المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲۵

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

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

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

پاسخ

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

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

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

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

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

$$2e \geq 3f \quad \Rightarrow \quad 2e \geq 3(e+2-7) \quad \Rightarrow \quad e \leq 15$$

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


ابزار صفحه