المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی دوم:دوره‌ی ۲۸:سوال یک

هدیه معین (۲۰ نمره)

مصطفی برای جشن تولدش. معین را دعوت کرده است. معین تصمیم گرفته کادوی تولد مصطفی را خودش بسازد. به دلیل علاقه‌ی مصطفی به گراف. معین یک گراف ساده‌ی ۲۰۱۸ رأسی با تعدادی توپ (به عنوان رأس) و میله (به عنوان یال) ساخته است.

روز قبل از تولد. معین یادش می‌آید مصطفی فقط گراف‌های ساده‌ای را دوست دارد که درجه‌ی تمام رآس‌ها در آن فرد است. معین می‌خواهد با اضافه کردن تعدادی میله (یال) به گراف کاری کند که درجه‌ی تمام رآس‌ها فرد شود و هم‌چنان گراف به صورت ساده باقی بماند.

و با بررسی گرافش متوجه شد تنها یک روش برای این کار وجود دارد! حداقل تعداد یال‌های ممکن برای گراف معین (قبل از اقدام برای اضافه کردن بیال‌ها) را بيابید.

پاسخ

تعریف:

  • لیست‌های بدون ترتیبعدم یال: اگر بین دو رأس در گراف یالی نباشد.
  • گراف مکمل گراف $G$: گرافی با همان رأس‌های گراف $G$ ولی یال‌هایش، عدم یال‌های $G$ است.

گراف معین را گراف $G$ و مکمل گراف معین را $\overline{G}$ می‌نامیم. معین اگر بجای تمامی عدم یال‌های گراف $G$ یک یال اضافه کند، هر رأس از $G$ به تمامی رئوس دیگر یال خواهد داشت. پس درجه هر رأس برابر با $2018 - 1 = 2017$ و فرد خواهد بود. پس این یک روش برای فرد کردن درجه رئوس گراف است و از آنجایی که معین تنها یک روش برای این کار دارد؛ پس تنها روش این است که معین تمامی یال‎های ممکن را بگذارد. گراف یال‌هایی که معین اضافه می‌کند همان گراف عدم یال‌ها یعنی $\overline{G}$ است. حال فرض کنید در $\overline{G}$ یک دور وجود داشته باشد. اگر معین یال‌های این دور را به گراف اضافه نکند باز هم درجه همه رئوس فرد می‌شود زیرا اگر یال‌های یک دور را در نظر بگیریم، هر رأس از گراف یا به $2$ یال متصل است یا به هیچ یالی متصل نیست. پس وجود یا عدم وجود یال‌های یک دور در گراف تغییری در زوجیت درجه رئوس بوجود نمی‌آورد. در نتیجه اگر در $\overline{G}$ یک دور وجود داشته باشد، معین هم می‌تواند یال‌‌های آن دور را به $G$ اضافه کند و هم می‌تواند اضافه نکند و این خود دو روش اضافه کردن یال‌ها است و با توجه به یگانه بودن روش‌ اضافه کردن یال‌ها؛ می‌توان نتیجه گرفت که $\overline{G}$ دور ندارد.

حال اثبات می‌کنیم گرافی که دور ندارد حداکثر $n-1$ یال دارد:

  • برهان خلف: فرض کنید گرافی داریم بدون دور که حداقل $n$ یال دارد. حال تعدادی یال از گراف حذف می‌کنیم تا گرافمان دقیقا $n-1$ یال داشته باشد. دقت کنید که با حذف کردن یال‌ها دوری در گراف بوجود نیامده و گراف همچنان بدون دور باقی می‌ماند. حال گرافی بدون دور و $n-1$ داریم. پس یک درخت داریم (درخت). حال اگر یال‌هایی که حذف کردیم را برگردانیم (یعنی به درختمان یکسری یال اضافه کنیم) حتماً گرافی دارای دور بوجود می‌‌آید (ویژگی درخت - ویژگی $6$ام) ولی گراف اولیه ما بدون دور بود، پس به تناقض رسیدیم و فرض خلف غلط است.

پس $\overline{G}$ با توجه به اینکه دور ندارد، حداکثر $n-1$ یال دارد. در نتیجه $G$ حداقل $\binom{2018}{2} - 2018 + 1$ یال دارد. حال برای تکمیل اثبات گرافی $2018$ رأسی می‌سازیم که در آن تنها یک روش برای فرد کردن درجه کل رئوس وجود داشته باشد و نیز دارای $\binom{2018}{2} - 2018 + 1$ یال باشد. گراف را اینگونه درست می‌کنیم: رئوس را از $1$ تا $2018$ شماره گذاری می‌کنیم. رأس $1$ را به رأس دیگری وضل نکرده ولی تمامی رئوس دیگر را به هم وصل می‌کنیم. حال گراف دقیقا $\binom {2017} {2}$ یا همان $\binom{2018}{2} - 2018 + 1$ یال دارد. و تنها روش فرد کردن درجه کل رئوس، وصل کردن رأس $1$ به همه‌ی آنها است. زیرا همه‌ی رئوس $2$ تا $2018$ دارای درجه زوج هستند و تنها روش تغییر درجه هر یک از آنها اضافه کردن یال بین رأس $1$ و رأس مورد نظر است. پس در آخر باید کلیه رئوس به یکدیگر متصل باشند و این تنها روش فرد کردن درجه رئوس است.
گفتیم که تعداد یال‌های گراف $G$ حداقل $\binom{2018}{2} - 2018 + 1$ است و نیز این مقدار با یک مثال قابل دستیابی است. پس جواب $\binom{2018}{2} - 2018 + 1$ یا همان $\binom {2017} {2}$ است.


ابزار صفحه