سیاره‌ی آلفا

در اول نقشه کشور ها را با یک گراف شبکه (گرافی که رأس ‌های آن نقاط شبکه‌اند) $m×n$ مدل‌سازی می‌کنیم. یعنی هر کشور یک نقطه و هر جاده هم یک یال بین دو نقطه متناظر است. سفر مورد نظر جهانگردان نیز یک دور همیلتونی (دوری شامل تمامی نقاط شبکه) است. طبق گفته‌ صورت سوال ما به دنبال پیدا کردن $2$ دور همیلتونی با یال‌های مجزا هستیم.

تعریف:
یک یال را یال خوب سطر $i$ می‌نامیم اگر و تنها اگر این یال بین دو نقطه $(i,j_1)$ و $(i,j_2)$ کشیده شده و نیز $|j_1-j_2|=n-1$ باشد.
یک یال را یال خوب ستون $j$ می‌نامیم اگر و تنها اگر این یال بین دو نقطه $(i_1,j)$ و $(i_2,j)$ کشیده شده و نیز $|i_1-i_2|=m-1$ باشد.

نکته: فعلا حالت $n$ فرد و $m$ زوج از مسئله را حل نمی‌کنیم.

حال روی $n$ با گام $2$ تایی استقرا می‌زنیم. $\Leftarrow$ زوجیت $n$ در حین استقرا ثابت می‌ماند و نیز $m$ هم همیشه در حین استقرا ثابت است.

• فرض استقرا: $2$ دور همیلتونی یال مجزا در گراف شبکه $m×n$ وجود دارد که یکی از دور ها شامل دقیقا یک یال خوب سطری باشد و نیز این یال، یال خوب سطر آخر باشد.
• پایه استقرا:
  • برای $n$ های زوج: حالت $n=4$:
  • برای $n$ های فرد و $m$ های فرد: حالت $n=3$ و $m$ فرد:

• گام استقرا: فرض می‌کنیم فرض استقرا برای گراف شبکه $m_0 \times n_0$ درست است این گراف را گراف شبکه اولیه می‌نامیم. طبق فرض استقرا در این گراف می‌توان دو دور همیلتونی مجزا یافت که یکی دقیقا یک یال خوب دارد و این یال، یال خوب سطر آخر است. این دور همیلتونی را دور خوب و دور همیلتونی مجزا از دور خوب را دور ناخوب می‌نامیم. حال می‌خواهیم فرض استقرا را برای گراف شبکه $m_0 \times ({n_0 +2 })$ اثبات کنیم. پس باید دو دور همیلتونی مجزا درون گراف شبکه $m_0 \times ({n_0 +2 })$ بیابیم که یکی از دور ها دارای دقیقا یک یال خوب سطری آنهم در سطر آخر باشد. برای اینکار در قدم اول، دورهایمان را از روی دور همیلتونی‌های شبکه $m_0 \times n_0$ می‌سازیم. بدین صورت که یال های شبکه $m_0 \times n_0$ وسطی (شامل ستون اول و آخر نباشد) از گراف شبکه $m_0 \times ({n_0 +2 })$ را مطابق با یکی از دور‌های خوب یا ناخوب قرار می‌دهیم. دقت کنید یال‌های خوب سطری می‌توانند در دور همیلتونی های فرض استقرا وجود داشته باشند ولی در شبکه $m_0 \times n_0$ وسطی به خاطر وجود ستون‌های در سمت چپ و راست شبکه این‌ یال نمی‌توانند موجود باشند ولی موقتا ما این یال‌های خوب سطری را به شبکه $m_0 \times n_0$ وسطی اضافه می‌کنیم.

• ساخت اولین دور همیلتونی: برای اینکار یال‌های $m_0 \times n_0$ وسطی را منطبق با دور خوب در نظر می‌گیریم. در ادامه یال‌های $(m_0,2) \leftrightarrow (m_0,1)$ و $(m_0,n_0+1)\leftrightarrow (m_0,n_0+2)$ را برای دور انتخاب می‌کنیم. سپس یال های غیر خوب ستون اول و آخر و نیز یال $(1,1)\leftrightarrow (1,n_0+2)$ را هم انتخاب می‌کنیم. گفتیم که یال‌های خوب سطری موجود در فرض استقرا را باید از $m_0 \times n_0$ وسطی حذف کنیم. با توجه به اینکه دور خوب فقط یک یال خوب سطری داشت (آنهم در سطر آخر)، پس با حذف این یال کار را تمام کرده و دور به طور کامل انتخاب می‌شود. حال با توجه به اینکه یال های $m_0 \times n_0$ وسط یک دور همیلتونی تشکیل می‌دادند، دور جدید نیز همه نقاط $m_0 \times n_0$ وسط را دیده و نیز تمامی نقاط دو ستون اول و آخر را هم می‌بیند پس این دور، دور همیلتونی است.
• ساخت دومین دور همیلتونی: در اول یال های گراف شبکه $m_0 \times n_0$ وسط را منطبق با دور ناخوب اتخاب می‌کنیم. دقت کنید که درجه هر راس در هر دور همیلتونی $2$ است پس باید تمامی $4$ یال متصل به هر راس در اجتماع $2$ دور همیلتونی‌های مجزا وجود داشته باشد، پس با توجه به اینکه دور خوب دقیقا یک یال خوب دارد و در دور همیلتونی دیگر این گراف شبکه (دور ناخوب) باید تمامی یال‎‌های خوب ناموجود در دور خوب، وجود داشته باشد پس $m_0-1$ یال خوب سطری به ترتیب در سطرهای $1,2,3...,m_0-1$، در دور ناخوب وجود دارد. گقته بودیم که یال‌های خوب سطری دور های همیلتونی فرض استقرا باید از شبکه $m_0 \times n_0$ وسطی دورمان حذف شوند. پس بجای یال خوب سطر $i$ ام در شبکه $m_0 \times n_0$ وسط ، $3$ یال‌ $\lbrace (i,1) \leftrightarrow (i,2) , (i,1)\leftrightarrow(i,n_0+2) , (i,n_0+1)\leftrightarrow(i,n_0+2) \rbrace$ را برای دورمان اتخاب می‌کنیم. بجز برای $i=1$ و $i=m_0$ که یال های مورد نیاز در این دو حالت را جداگانه اضافه می‌کنیم. در حالت $i=1$ به خاطر اینکه یال خوب این سطر در اولین دور همیلتونی که ساختیم استفاده شده، پس فقط دو یال $\lbrace (i,1) \leftrightarrow (i,2) , (i,n_0+1)\leftrightarrow(i,n_0+2) \rbrace$ را انتخاب کرده و به جای یال خوب سطر $1$ یال های خوب ستون‌های $1$ و $n_0+2$ را انتخاب می‌کنیم. برای $i=m_0$ هم دو یال $\lbrace (m_0,1) \leftrightarrow (m_0,2) , (m_0,n_0+1)\leftrightarrow(m_0,n_0+2) \rbrace$ در ساخت دور همیلتونی‏‏$2$ استفاده شده‌اند، پس در این حالت با توجه به اینکه یال های خوب ستون های اول و آخر در حالت قبل برای دور اتخاب شده‌اند، ما فقط یال خوب سطر $m_0$ را اضافه می‌کنیم و بدین ترتیب ساخت دورمان تمام می‌‌شود و با توجه به نحوه چینش یال‌ها و فرض استقرا مجموعه یال های این دور یک دور همیلتونی را تشکیل می‌دهند.
• مجزا بودن: با کمی دقت متوجه می‌شوید که یال های دور همیلتونی$2$ مجزا از یال های دور همیلتونی $1$ اند. زیرا طبق فرض استقرا و با توجه به نحوه ساخت دورها، تمامی یال های انتخاب شده در گراف شبکه $m_0 \times n_0$ وسط در این دو دور همیلتونی از هم مجزا‌اند و نیز یال هایی که ما در گام استقرا اضافه کردیم هم از هم مجزااند.
• کامل شدن فرض استقرا: حال در ساخت دور همیلتونی$1$ از یک یال خوب سطری استفاده شد که این یال، یال خوب سطر اول است. پس برای برآورده شدن کامل فرض استقرا باید دو گراف شبکه و دور همیلتونی‌ها را نسبت به خط افق تقارن دهیم تا یال خوب سطری، سطر اول تبدیل به یال خوب سطری، سطر آخر شده و نیز دو دور همیلتونی مجزا بمانند.

در طی گام استقرا زوجیت $m$ و $n$ حفظ می‌شود پس هیچ وقت از فرض استقرا برای گراف شبکه $m_0 \times n_0$ ای که $n$ فرد و $m$ زوج باشد، استفاده نشده و استقرا درست است.

حال برای بدست آوردن دور های همیلتونی برای گراف شبکه $m \times n$ای که $n$ فرد و $m$ زوج باشد، جواب برای گراف شبکه $n \times m$ را درنظر بگیرید (چون تعداد ستون ها زوج است، وجود دارد). نقطه $(i,j)$ را به نقطه $(j,i)$ تناظر داده و نیز یال‌های بین نقاط در حالت اولیه را تبدیل به یال‌هایی بین نقاط متناظر کنید. بدین ترتیب دور ها مجزا و همیلتونی می‌مانند پس جواب برای این حالت نیز بدست می‌آید.