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

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

در این بخش در مورد مسائلی بحث می کنیم که به شما کمک می کند شهود بهتری نسبت به درخت ها پیدا کنید همچنین دید و قدرت حل مسئله شما را افزایش می دهد. حتما قبل از خواندن حل سوالات، به اندازه کافی روی آنها فکر کنید!

مربع پاک کن

یک دستگاه مربع پاک کن در اختیار داریم که در هر مرحله می تواند \(C_4\) از گراف را در نظر گرفته و یکی از یال های آن را حذف کند. در ابتدا یک \(K_n\) با \(n \geq 4\) داریم. هدف ما این است که طوری از مربع پاک کن استفاده کنیم که در نهایت تعداد یال های باقی مانده در گراف کمینه شود. این تعداد کمینه را بیابید.

حل

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

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

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

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

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

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

عدد گذاری روی یال

یک گراف همبند داریم که \(m\) یال دارد. می خواهیم یال های این گراف جایگشتی از اعداد 1 تا \(m\) را نسبت بدهیم به طوری که به ازای هر راس \(v\) که درجه آن بیشتر از 1 است، ب.م.م اعداد روی یال های مجاور \(v\) برابر با 1 باشد.

حل

برای حل سوال از این نکته استفاده می کنیم که ب.م.م هر دو عدد متوالی برابر با 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 > 1\) راسی که راس درجه 2 ندارد تعداد برگ ها بیشتر از غیر برگ هاست.

حل

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

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

  • راس \(v\) از برگ بودن خارج می شود.
  • تمام بچه های \(v\) به مجموعه برگ ها اضافه می شوند.

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

نکته

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

جادوی bfs

یک گراف همبند داریم.می دانیم اگر هر دور فردی از این گراف را در نظر بگیرید و یال های این دور را حذف کنید گراف ناهمبند می شود. ثابت کنید می توان راس های این گراف را با 4 رنگ، رنگ آمیزی کرد به طوریکه هر دو راس مجاور رنگ متفاوت داشته باشند!

حل

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

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

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

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

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