====== سوال ۲۷ ======



یک گراف کامل
$11$
رأسی با  رأس‌های
۰، ۱، ۲، $\ldots$ 
و ۱۰
داریم. روی یال بین رأس‌های $i$ و  $j$
مقدار باقی‌مانده‌ی
$i+j$
در تقسیم بر
$11$
را نوشته‌ایم. می‌خواهیم یک زیردرخت فراگیر از این گراف انتخاب کنیم، طوری که مجموع اعداد یال‌های آن کمینه باشد. این مقدار کمینه چیست؟
  - ۱۶
  - ۱۰
  - ۱۱
  - ۶
  - ۵
<راهنمایی>
پیشنهاد می‌شود در مورد الگوریتم [[https://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%DA%A9%D8%B1%D8%A7%D8%B3%DA%A9%D8%A7%D9%84|کروسکال (کراسکال)]] مطالعاتی داشته باشید.
</راهنمایی>

<راهنمایی>
بنا بر راهنمایی پیشین، یال‌ها را به ترتیب وزن اضافه کنید.
</راهنمایی>

<پاسخ>
 گزینه‌ی ۵ درست است.



تعداد یال‌های درخت برابر ۱۰ است. گراف پنج یال با عدد ۰  دارد. پس پاسخ نمی‌تواند از
$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$$
پس پاسخ برابر ۵ است.
</پاسخ>

  * [[سوال ۲۶|سوال قبل]]
  * [[سوال ۲۸|سوال بعد]]