یک گراف کامل $11$ رأسی با رأسهای ۱، ۲، $\ldots$ و ۱۰ داریم. روی یال بین رأسهای $i$ و $j$ مقدار باقیماندهی $i+j$ در تقسیم بر $11$ را نوشتهایم. میخواهیم یک زیردرخت فراگیر از این گراف انتخاب کنیم، طوری که مجموع اعداد یالهای آن کمینه باشد. این مقدار کمینه چیست؟
پاسخ
گزینهی ۵ درست است.
تعداد یالهای درخت برابر ۱۰ است. گراف پنج یال با عدد ۰ دارد. پس پاسخ نمیتواند از $5 \times 0 + (10-5) \times 1 = 5$ کمتر باشد.
حال اگر یالهای زیر را به عنوان یالهای درخت در نظر بگیریم، مجموع اعداد یالهای درخت برابر ۵ خواهد شد: $$1 \leftrightarrow 10 \qquad 2 \leftrightarrow 9 \qquad 3 \leftrightarrow 8 \qquad 4 \leftrightarrow 7 \qquad 5 \leftrightarrow 6 \qquad $$ $$0 \leftrightarrow 1 \qquad 2 \leftrightarrow 10 \qquad 3 \leftrightarrow 9 \qquad 4 \leftrightarrow 8 \qquad 5 \leftrightarrow 7 \qquad$$ پس پاسخ برابر ۵ است.