Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۲۷:سوال ۲۷

سوال ۲۷

یک گراف کامل 11 رأسی با رأس‌های ۰، ۱، ۲، و ۱۰ داریم. روی یال بین رأس‌های i و j مقدار باقی‌مانده‌ی i+j در تقسیم بر 11 را نوشته‌ایم. می‌خواهیم یک زیردرخت فراگیر از این گراف انتخاب کنیم، طوری که مجموع اعداد یال‌های آن کمینه باشد. این مقدار کمینه چیست؟

  1. ۱۶
  2. ۱۰
  3. ۱۱
  4. ۶
  5. ۵

راهنمایی

پیشنهاد می‌شود در مورد الگوریتم کروسکال (کراسکال) مطالعاتی داشته باشید.

راهنمایی

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

پاسخ

گزینه‌ی ۵ درست است.

تعداد یال‌های درخت برابر ۱۰ است. گراف پنج یال با عدد ۰ دارد. پس پاسخ نمی‌تواند از 5×0+(105)×1=5 کم‌تر باشد.

حال اگر یال‌های زیر را به عنوان یال‌های درخت در نظر بگیریم، مجموع اعداد یال‌های درخت برابر ۵ خواهد شد: 11029384756 01210394857 پس پاسخ برابر ۵ است.


ابزار صفحه