گراف پترسن دور هامیلتونی ندارد - اثبات کامل- آزمون تیزهوشان نهم به دهم - خرداد ۹۷

متن زیر را با دقت بخوانید.

در نقشهٔ زیر، $10$ «شهر» با دایره‌های کوچک و $15$ «جاده» بین آنها با پاره‌خط نشان داده شده‌اند. منظور از یک «جاده»، پاره‌خطی مانند $AB$ است که دو رأس آن، روی دو شهر باشد. می‌دانیم که فقط در شهرها می‌توان از یک جاده به جادهٔ دیگر رفت.

با توجه‌به متن بالا، به پرسش‌ زیر پاسخ دهید.

دربارهٔ درستی جملات زیر چه می‌توان گفت؟
الف: می‌توانیم از یک شهر شروع به حرکت کنیم و بدون اینکه از شهر تکراری عبور کنیم، همهٔ $9$ شهر دیگر را ببینیم.
ب: می‌توانیم از یک شهر شروع به حرکت کنیم و بدون اینکه از شهر تکراری عبور کنیم، $9$ شهر دیگر را ببینیم و دوباره به همان شهر اول برگردیم.
۱) هر دو جمله درست است.
۲) تنها جملهٔ «الف» درست است.
۳) تنها جملهٔ «ب» درست است.
۴) هیچ‌یک درست نیستند.

راهنمای حل

جملهٔ «الف» درست است. (چرا؟)

پاسخ را نشان بده!

توجه کنید با اینکه با اندکی آزمون و خطا می‌توان تقریباً مطمئن شد که جملهٔ «ب» نادرست است، اما در اینجا می‌خواهیم اثبات دقیق و کاملی برای نادرستی جملهٔ «ب» بیاوریم.

فرض کنیم مسیری به نام «مسیر $X$» وجود داشته باشد که از یک شهر شروع شود و بدون اینکه از شهری تکراری عبور کند، $9$ شهر دیگر را بپیماید و دوباره به همان شهر اول برگردد؛ یعنی جملهٔ «ب» درست باشد. در ادامه، با بررسی حالت‌های مختلف نشان می‌دهیم که چنین چیزی امکان‌پذیر نیست؛ یعنی مسیر $X$ نمی‌تواند وجود داشته باشد.

مسیر $X$ می‌تواند از هر شهری شروع شود. (چرا؟)

پاسخ را نشان بده!

فرض کنیم مسیر $X$ با جادهٔ $IA$ شروع شود. بنابراین، از شهر $A$ یا باید شهر $B$ برویم یا به شهر $E$. به‌دلیل تقارن موجود در شکل، فرقی نمی‌کند که مسیر ما با $IAB$ شروع شود یا با $IAE$. فرض می‌کنیم که مسیر $X$ با $IAB$ شروع شده باشد.

حال، از شهر $B$ یا باید به شهر $C$ برویم یا به شهر $G$. واضح است که در مسیر $X$ باید راهی وجود داشته باشد که با استفاده از آن بتوان از $C$ به $G$، یا از $G$ به $C$ رفت به‌طوری‌که شهرهای $I$، $A$، و $B$ را ندید. (چرا؟)

پاسخ را نشان بده!

در نتیجه، برای بررسی همهٔ راه‌هایی که می‌توان از $G$ به $C$، یا از $C$ به $G$ رفت، نیازی به شهرهای $I$، $A$، و $B$، و جاده‌های متصل به آنها نداریم.