Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۴:گراف:سوال ۸

دور هامیلتونی ۲

اولا واضح است که اگر حکم مسئله را برای درخت‌ها ثابت کنیم. برای کل گرف‌ها ثابت می‌شود، چرا که هر گراف همبند G حداقل یک زیردرخت فراگیر T دارد و همه‌ی یال‌هایی که در T3 وجود دارند در G3 هم موجود هستند. برای اثبات حکم روی درخت‌ها از استقرا استفاده می‌کنیم: «به ازای هر درخت T با n راس، T3 شامل حداق یک دور هامیلتونی C است». حال سعی می‌کنیم روی n‌ استقرا بزنیم ولی با کمی دقت متوجه می‌شویم که این کار عملی نیست. برای رفع این مشکل حکم استقرا را تقویت می‌کنیم: «به ازای هر درخت T با n راس، و هر یال (eT)e، گراف T3 شامل حداقل یک دور هامیلتونی C‌ است به طوری که eC». حال می‌توان حکم را اثبات کرد: فرض می‌کنیم حکم برای هر درخت با k‌راس که 2<kn اثبات شده باشد. می‌خواهیم حکم را برای n‌اثبات کنیم:

اگر یال e‌ را از T حذف کنیم دو درخت جدید T1 و T2‌تشکیل خواهند شد. اگر فرض کنیم هر دو درخت T1 و T2 بیش از دو راس دارند (در غیر این صورت هم حکم به همین روش اثبات می‌شود) می‌توان فرض استقرای قوی شده را مانند شکل زیر روی آن‌ها اعمال کرد: T1 شامل دور هامیلتونی C1 است که e1 را دربر داشته باشد و T2 هم شامل دور هامیلتونی C2 است که e2 جزء آن باشد. می‌دانیم که در T3 دو راس x‌ و y به هم یال دارند. بنابراین اگر e1 را از C1‌و e2 را از C2 حذف کنیم و به مجموعه‌ی باقی‌مانده یال‌های e و xy را اضافه کنیم، مجموعه به دست آمده یک دور هامیلتونی در T3 خواهد بود که شامل e هم هست.


ابزار صفحه