کارگاه پرورش ایده¶

حل¶

مربع پاک کن به دو ویژگی لطمه نمی زند.

1. همبندی گراف حفظ می شود.

2. همواره دور فرد خواهد داشت.

شاید مورد دوم کمی سخت تر به ذهن برسد. احتمالا شما هم در ابتدا حدس زدید که جواب باید $n-1$ باشد (به دلیل ویژگی اول) اما هر طور که از مربع پاک کن استفاده بکنید یک دور مزاحم باقی می ماند!

برای ویژگی دوم ابتدا توجه کنید که چون $n\ge 3$ پس حتما در ابتدا یک دور فرد داریم. فرض کنید که از مربع $ABCD$ یال $AB$ را حذف کردیم و دور فردی که در مرحله قبل داشتیم از بین رفت. حالا دور فرد قبلی را طی کنید فقط به جای استفاده از یال $AB$ از گشت $ACDB$ استفاده کنید. واضح است که در نهایت به یک گشت فرد می رسیم که همانطور که در فصل 1 گفتیم درون هر گشت فرد دور فردی وجود خواهد داشت!

از دو مورد گفته شده می توانیم نتیجه بگیریم که به دلیل همبندی گراف باید حداقل $n-1$ یال داشته باشیم و از آنجایی که اگر دقیقا $n-1$ یال همبند داشته باشیم یک درخت داریم که دور فرد ندارد، پس باید حداقل $n$ یال داشته باشیم.

ساخت مثال با دقیقا $n$ یال را به عهده خواننده می گذاریم!

حل¶

برای حل سوال از این نکته استفاده می کنیم که ب.م.م هر دو عدد متوالی برابر با 1 است.

از یک راس دلخواه شروع به اجرای dfs بکنید و به اولین یالی که می بینیم عدد 1، به دومین یالی که می بینیم عدد 2 و به همین ترتیب. منظور از دیدن یال این چیست؟ فرض کنید روی راس $u$ هستیم و در حال انجام dfs هستیم. لیست کل یال های مجاور $u$ را به ترتیب نگاه می کنیم. وقتی به یال $uv$ می رسیم در صورتیکه قبلا به این یال عددی نسبت داده نشده بود ما یک عدد نسبت می دهیم. سپس اگر راس $v$ غیرتکراری بود dfs(v) را صدا می زنیم.

پس عددی که به هر یال نسبت می دهیم برابر است با اینکه این یال، چندمین یال دیده شده است. ب.م.م اعداد یال های مجاور ریشه 1 است زیرا که اولین یالی که طی می کنیم 1 است و مجاور ریشه می باشد. به ازای هر راس غیر ریشه مثل $u$ ب.م.م اعداد مجاور $u$ برابر با 1 است، زیرا که اگر با یال با شماره $x$ به $u$ وارد شده باشیم طبق منطق بازگشتی dfs بلافاصله روی یکی از یال های مجاور $u$ عدد $x+1$ را خواهیم نوشت (مگر اینکه درجه راس $u$ برابر با 1 باشد که در اینصورت روی این راس محدودیت خاصی نداریم).

توجه کنید که به خاطر ساختار dfs هر کدام از backedge ها که جزو یال های درخت نیستند را از راس پایینی آن می بینیم! (چرا؟) بنابرین برای برگ های درخت که درجه آنها 1 نیست مشکلی پیش نمی آید.

حل¶

برای حل سوال از استقرا استفاده می کنیم. پایه استقرا را $n=2$ می گذاریم که درستی آن واضح است. درخت $T$ را از یک راس دلخواه آویزان می کنیم و پایین ترین برگ را $u$ می نامیم. فرض کنید پدر پایین ترین برگ $v$ باشد. در اینصورت همه بچه های $v$ برگ هستند (چرا؟). اگر $v$ همان ریشه باشد که حکم واضح است (چون به جز $v$ بقیه راس ها برگ هستند). در غیراینصورت با حذف تمام بچه های $v$ که برگ هستند به درخت $T^{\prime }$ با تعداد راس کمتر می رسیم که حداقل 2 راس دارد و راس درجه 2 ندارد پس فرض استقرا برای آن برقرار است. فرض کنید در این درخت تعداد برگ ها $A^{\prime }$ و تعداد غیربرگ ها $B^{\prime }$ باشد و طبق فرض استقرا $A^{\prime }>B^{\prime }$ است.

حالا دوباره بچه های $v$ را اضافه کنید. اگر $d$ تا بچه داشته باشد آنگاه تغییراتی که در درخت اعمال می شود به اینصورت است.

• راس $v$ از برگ بودن خارج می شود.

• تمام بچه های $v$ به مجموعه برگ ها اضافه می شوند.

پس اگر تعداد برگ ها و غیر برگ های جدید را به ترتیب $A,B$ بنامیم داریم $A=A^{\prime }+d-1$ و $B=B^{\prime }+1$ و از آنجایی که $d>1$ است پس همچنان $A>B$ برقرار است.

نکته¶

مسئله ای که گفته شد یک لم کلاسیک بود که در حل بعضی مسائل به ما کمک می کند. به طور کلی در بعضی از مسائل می توانیم راس های درجه 2 را فشرده کرده و آنها را از بین ببریم. یعنی اینکه اگر تمام راس های درجه 2 درخت را قرمز کنیم، راس های درجه 2 تشکیل تعدادی مسیر مجزا می دهند (چرا؟). حالا فرض کنید به ازای هر مسیر متشکل از راس های درجه 2 که از راسی مثل $A$ شروع شده و به راسی مثل $B$ ختم می شود این مسیر را حذف کنیم و فقط یالی از $A$ به $B$ بگذاریم. بعد از انجام این عملیات ها تمام راس های درجه 2 از بین می روند و ساختار کلی درخت حفظ می شود. حالا اگر درخت مسئله به گونه ای باشد که تعداد برگ ها کم باشد می توان نتیجه بگیریم تعداد کل راس های درخت هم کم است!

حل¶

اگر نمی دانستیم باید به bfs فکر کنیم این سوال چقدر سخت می شد؟

حالا از یک راس دلخواه bfs بزنید. حالا گراف به تعدادی لایه افراز شده است که یال های گراف یا درون یک لایه اند یا بین دو لایه مجاور هستند.

ادعا می کنیم زیرگراف شامل راس های هر کدام از لایه ها دوبخشی است. برهان خلف بزنید و فرض کنید یک لایه داریم که دوبخشی نیست. پس باید دور فرد داشته باشد. حالا اگر لایه های این دور فرد را حذف کنید طبق صورت سوال باید گراف ناهمبند شود اما می دانیم که این اتفاق نمی افتد! زیرا که گراف توسط یال های درخت bfs همبند شده است و یال های درخت bfs تنها بین لایه های مجاور است.

پس اثبات کردیم که هر کدام از لایه ها دوبخشی است. پس هر لایه را می توانیم با دو رنگ، رنگ آمیزی کنیم که مجاور ها رنگ متفاوت داشته باشند. حالا لایه های فرد را با رنگ 1, 2 و لایه های زوج را با رنگ 3, 4 رنگ کنید. مشکلی پیش نمی آید زیرا دو راس که همرنگ اند یا درون یک لایه اند‌ (که با دوبخشی بودن مشکل را برطرف کردیم) یا در لایه های مجاور نیستند (که یالی بین آنها وجود ندارد).

به همین سادگی!