آمار پرسش:
- پرسیده شده: 2023-03-26 07:00:24 -0600
- مشاهده شده: 114 بار
- بروز شده: 2023-03-26 09:09:59 -0600
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
مسئله ترکیبی از گراف و اصل لانه کبوتری
یال های گراف کامل از مرتبه 2n+1 را با n رنگ رنگ کردیم ثابت کنید دوری تک رنگ در گراف رنگ شده وجود دارد
1 پاسخ
از آنجایی که گراف کامل است پس دقیقا n(2n+1) یال دارد. و چون این گراف با n رنگ، رنگ آمیزی شده پس طبق اصل لانه کبوتری حتما رنگی وجود دارد که از آن حداقل 2n+1 بار استفاده شده باشد. چنین رنگی را A می نامیم. سپس تمام یالهایی که رنگی غیر از A دارند را حذف می کنیم. بدیهی است که طبق گفته های قبلی، حداقل 2n+1 یال باقی می ماند که همه ی آنها به رنگ A هستند. گراف حاصل شده را G(A)می نامیم. حال با استفاده از قضیه ی زیر، حکم مسئله نتیجه می شود:
قضیه: در گرافی با n راس و m یال، اگر m بزرگتر یا مساوی n باشد، حتما در گراف دور وجود دارد (به عبارتی اگر تعداد یال های گراف حداقل به اندازه ی تعداد راس ها باشد حتما در گراف دور وجود دارد)
با توجه به اینکه طبق فرض سول، تعداد راس های گراف 2n+1 است و گراف G(A) نیز حداقل 2n+1 یال دارد ، بنابراین در G(A) حتما دور وجود دارد. همچنین چون G(A) زیر گراف گراف اصلی است، پس حتما در گراف کامل نیز دوری وجود دارد که همه ی یال های آن به رنگ A هستند و حکم اثبات می شود...
