Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۵

فرض کنید که شهرهای ‎۱‎ تا ‎۷‎ دور دایره‌ای به شکل مقابل می‌باشند. (بین شهرهای مجاور جاده وجود دارد.)‎

حداکثر چند جاده‌ی دیگر می‌توان بین این شهرها کشید به طوری که هیچ دو جاده‌ای هم‌دیگر را قطع نکنند و بین هر دو شهر حداکثر یک جاده‌ی مستقیم وجود داشته باشد. (جاده‌ها هم می‌توانند در داخل دایره و هم در خارج آن کشیده شوند‎.‎)

  1. ۶
  2. ۷
  3. ۸
  4. ۹
  5. ۱۰‎

پاسخ

گزینه (۳) درست است.

ابتدا با توجه به قضیه‌ی اولر ثابت می‌کنیم تعداد جاده‌های مورد نظر نمی‌تواند بیش از ۸ جاده باشد.

قضیه‌ي اولر به یکی از دو صورت زیر بیان می‌شود:

  1. اگر v تعداد رئوس٬ e تعداد یال ها و f تعداد وجوه یک چند وجهی باشد آن‌گاه e+2=v+f.
  2. اگر v تعداد رئوس٬ e تعداد یال ها و f تعداد نواحی موجود در یک گراف همبند باشد(ناحیه‌ی نامحدود خارجی نیز شمرده می‌شود) آن‌گاه e+2=v+f.

هر ناحیه در دور خود حداقل سه یال دارد٬ بنابراین تعداد یال‌های موجود در دور تمام نواحی حداقل برابر 3f می‌باشد ولی چون هر یال دقیقا مرز دو ناحیه می‌‌باشد٬ با این شمارش هر یک از آن‌ها دو بار شمارش می‌شوند٬ بنابراین:

2e3f2e3(e+27)e15

چون در شکل داده شده ۷ یال رسم شده پس حداکثر ۸ یال دیگر مطابق شکل زیر می‌توان رسم کرد:


ابزار صفحه