قضیه های وجودی دور همیلتونی¶

لم اساسی¶

گراف ساده \(n\) راسی \(G\) را در نظر بگیرید که دارای دو راس نامجاور \(a, b\) می باشد به طوریکه \(d_a + d_b \geq n\). حالا گراف \(H\) را در نظر بگیرید که همان گراف \(G\) است که در آن رئوس \(a, b\) با یک یال به هم متصل شده اند. ادعا می کنیم گراف \(G\) دور همیلتونی دارد اگر و تنها اگر گراف \(H\) دور همیلتونی داشته باشد.

طرف اول اثبات واضح است زیرا اگر \(G\) دور همیلتونی داشته باشد \(H\) هم دارای آن دور خواهد بود. (یالی حذف نکردیم)

حالا برای اثبات طرف دوم فرض کنید \(H\) دور همیلتونی داشته باشد. اگر این دور از یال \(ab\) استفاده نکند \(G\) هم همان دور را دارد و حکم اثبات می شود. پس فرض کنید این دور از یال \(ab\) استفاده می کند در نتیجه باید مسیری همیلتونی در \(G\) وجود داشته باشد که از \(a\) شروع و به \(b\) ختم می شود.

حالا فرض کنید مسیر همیلتونی ما \(a = v_1, v_2, ..., v_n = b\) می باشد. اگر \(v_1\) به \(v_i\) یال داشته باشد و \(v_n\) به \(v_{i-1}\) یال داشته باشد آنگاه می توانیم یک دور همیلتونی در گراف \(G\) بیابیم. (از \(v_1\) به مستقیم به \(v_i\) بروید سپس مسیر \(v_i\) تا \(v_n\) را طی کنید سپس از \(v_n\) مستقیم به \(v_{i-1}\) بروید سپس مسیر \(v_{i-1}\) تا \(v_1\) را طی کنید).

حالا به ازای هر راسی مثل \(v_i\) که \(v_1\) به آن یال دارد \(v_{i-1}\) را قرمز کنید و به ازای هر راسی مثل \(v_i\) که \(v_n\) به آن یال دارد \(v_i\) را آبی کنید. اگر بتوانیم ثابت کنیم راسی وجود دارد که هم قرمز هم آبی شده باشد مسئله حل خواهد شد. می دانیم که طبق فرض \(d_a + d_b \geq n\) پس تعداد راس هایی که رنگ کردیم حداقل \(n\) است. از طرفی راس \(v_n\) هیچگاه رنگ نمی شود (چرا؟). پس \(n-1\) راس داریم که حداقل \(n\) بار رنگ شده اند پس طبق اصل لانه کبوتری راسی وجود دارد که دو بار رنگ شده باشد. پس راسی وجود دارد که همزمان آبی و قرمز شده باشد در نتیجه در \(G\) دور همیلتونی وجود دارد.

دیگر قضایا¶

در اینجا به بیان چند قضیه می پردازیم که می توانید به راحتی با لم اساسی که بیان شد اثبات کنید.

• اگر در گراف \(G\) درجه هر راس حداقل \(\frac{n}{2}\) باشد آنگاه در این گراف دور همیلتونی وجود دارد.
• اگر در گراف \(G\) به ازای هر دو راس نامجاور \(a\) و \(b\) داشته باشیم \(d_a + d_b \geq n\) در این گراف دور همیلتونی وجود دارد.