====== سوال ۲۵ ======
{{:سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۸:258.png |}}
فرض کنید که شهرهای ‎۱‎ تا ‎۷‎ دور دایره‌ای به شکل مقابل می‌باشند. (بین شهرهای مجاور جاده وجود دارد.)‎

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

  - ۶
  - ۷
  - ۸
  - ۹
  - ۱۰‎
<پاسخ>
گزینه (۳) درست است.



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

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

  - اگر $v$  تعداد رئوس٬ $e$  تعداد یال ها و $f$  تعداد وجوه یک چند وجهی باشد آن‌گاه $e+2=v+f$.
  - اگر $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$$

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


{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۸:25.png |}}


</پاسخ>
  * [[سوال ۲۶|سوال بعد]]
  * [[سوال ۲۴|سوال قبل]]