بابا سوال آسون تر این حرفاست راهش کوتاهه...

n+1 راس رو ببرین دسته 1 و n-1 راس باقمیمونه هم ببرین دسته 2.حالا هر مرحله تو دسته 1 یه جاده خاکی رو بگیرین و n-1 راس باقیمونده از دسته 1 رو با کل راس های دسته 2 یه تطابق دلخواه بزنین.

پس از تعدادی مرحله همه جاده های دسته اول آسفالت میشه.حالا دوتا راس دلخواه از دسته 1 رو ببرین دسته 2 و برای دسته 2 هم همون کار رو که برا دسته 1 کرده بودیم انجام بدین.

گرافی با $2n$ راس در نظر بگیرید که هر راس بیانگر یکی از شهرهاست ، بین راس $i$ و راس $j$ یال میگذاریم ، اگرو فقط اگر بین این دوشهر جاده خاکی وجود داشته باشد .

لم ) اگر گراف جاده های خاکی ، گرافی دوبخشی باشد ، مسئله حل شده است .

در اینصورت رئوس موجود در هر بخش ، دو به دو با جاده آسفالت به هم متصل اند ، پس گراف به دوبخش با شرایط سوال تقسیم می شود .

ابتدا گراف را به شکل دلخواه به دو دسته ، هر یک شامل $n$ راس تقسیم می کنیم ، فرض کنید در دسته اول $x$ یال و در دسته دوم $y$ یال $(x>y)$ داشته باشیم .روشی ارائه می دهیم که کلیه یال ها درون این بخش ها را حذف کنیم.، اگر هم $x$ و هم $y$ از بزرگتر از 0 باشند در اینصورت در هر مرحله یک یال در هر دوبخش حذف می کنیم ، $n-2 $ یال باقی مانده رو هم به دلخواه $n-2 $راس در یک بخش را به $n-2$ راس در بخش دیگر وصل می کنیم ( دقت کنید این یال های بین دوبخش هیچ اهمیتی ندارند) ، بنابراین پس از مدتی به این وضعیت می رسیم که در یک دسته دوم 0 یال ، و در دسته اول $x-y$ یال داریم (اگر در ابتدا $x=y$ بود که مسئله حل شده است)

اکنون روش جدید ارائه میدهیم ، در هر مرحله 1 یال از بخش اول و دو راس دلخواه از دسته دوم انتخاب می کنیم و $n-2$ یال را نیز به دلخواه از$n-2$ راس بخش اول و $n-2$ راس بخش دوم انتخاب میکنیم ، تعداد یال های درون دسته ها تغییر نمی کند ، ولی در دسته دوم 1 یال و در دسته اول $x-y-1$ یال داریم ، سپس روش قبل را یکبار انجام میدهیم و دوتا از تعداد یالهای بین دسته ها کم میشود ، بنابراین پس از این عملیات ، یا همه ی یال های بین دسته ها از بین می روند که مسئله حل میشود یا تنها در یکی از دسته ها یک یال می ماند .

این یال را در نظر می گیریم ،یکی از راسهای دو سر این را در نظر میگیریم ، اگر هیچ یالی به دسته دیگر نداشته باشد ، در اینصورت مسئله حل میشود (این راس را وارد بخش دیگر میکنیم)

فرض کنید این راس ، $t$ تا یال به دسته دیگر داشته باشد ، $t$ مرحله به این شکل انجام میدهیم که هر مرحله 1 یال از این $t$ یال را انتخاب و $n-1$ یال دیگر را به دلخواه از $n-1$ راس دو بخش انتخاب میکنیم ، بنابراین در این حالت هم مسئله حل میشود !

ابتدا گراف را تشکیل می دهیم به این صورت که به ازای هر شهر یک راس و به ازای هر جاده خاکی یال قرمز و به ازای جاده آسفالت یال آبی می گذاریم.

لم) گراف زوج راسی k منتظم با یال های یکرنگ تطابق کامل دارد.

اثبات لم) هر بار یال راس u را با یکی از همسایه هایش می گیرم در زوج راس دیگه درجه هرراس k است و می توانم از فرض استقرا استفاده کنم.

لم1)اگر تمام یال های گراف کامل 2n راسی یک رنگ باشد می توان تمام یال ها را با استفاده از عملیات سوال ( گرفتن تطابق کامل ) به رنگ دیگر درآورد.

اثبات لم1) با استفاده از لم هر بار یک تطابق کامل گرفته یال های انرا آبی کرده و حدف می کنیم درجه هرکی 1 واحد کم شده ومیتوان از لم استفاده کرد.

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

اثبات لم2 ) هر بار این راس دلخواه را با یکی از همسایه هایش می گیرم که یال قرمز دارد و باقی تطابق را دلخواه می گیرم هربار یال های قرمز متصل به راس دلخواه کم می شود تا تمام شود.

اثبات سوال

پایه استقرا ) بدیهی گراف 2 راسی.

فرض استقرا ) هر گراف کامل 2n راسی با یال های آبی و قرمز را میتوان به دو دسته (نه لزوما برابر) افراز کرد طوری که یال های هر دسته همه آبی باشد.

حکم استقرا ) با استفاده از فرض برای هر گراف کامل 2n+1 راسی نیز اثبات کنید.

اثبات حکم استقرا ) با استفاده از لم2 یال های راس u را آبی می کنیم.حال سه حالت به وجود می آید:

i)تمام یال ها به غیر از یال های متصل به u قرمز است.برای حل این قسمت در باقی راس ها یال راس v را با u همیشه گرفته و باقی یال های راس های دیگر را طبق لم1 می توان آبی کرد.هال تمام راس هارا به غیر از v را در یک دسته و v را در یک دسته دیگر می گداریم ( بدیهی درست !!!!)

ii)حداقل یک یال آبی در بین تمام یال ها به جزیال های متصل به u وجود.برای حل این قسمت فرض کنید یال بین دو راس x و y آبی باشد حال این طور عمل می کنیم که 2راس x و u با هم میگریم و در 2n راس دیگه می توان طبق لم2 یال های متصل به راس y را آبی کرد حال دو راس u و y را کنار گداشته و در 2n راس باقی طبق فرض استقرا می توان به دو دسته افراز کرد حال دو راس uوy در دسته ای می ذاریم که x در آن نباشد( بدیهی درست !!!!)

iii)تمام یال ها به غیر از یال های متصل به u آبی است.( بدیهی درست !!!!)

یک گراف کامل 2n راسی می سازیم و یال بین دو راس را قرمز می کنیم، اگر بین شهرهای متناظرشون جاده آسفالت بود؛ در غیر اینصورت یال بینشون رو آبی می کنیم.

لم1: دو راس هستن که تعداد یالهای قرمز (و همچنین آبی) متصل بهشون با هم برابره. اثباتشم با لانه کبوتریه (دقت کنید هیچ دو راسی وجود ندارند که یکی تعداد یالهای آبی متصل بهش 2n-1 و دیگری صفر باشه. دیگه بقیه شو حال ندارم بنویسم)

لم 2: برای دو راسی که تعداد یالهای آبی شان یکسان است، می توان کاری کرد که تمام یالهای آبی شان (البته به غیر از یال بین خود این دو راس) قرمز بشن و قرمزها هم، همچنان قرمز باقی بمونن. اثباتشم اینجوریه که باید تو هر مرحله یک یال آبی از راس اول و یک یال آبی از راس دوم انتخاب کنیم که البته، به دو راس مختلف وصل باشن؛ بعد هم 2n-4 راس باقیمونه رو دلخواه جفت کنیم و عملیات تبدیل یال آبی به قرمز و قرمز به آبی (همون تبدیل آسفالت به خاکی و خاکی به آسفالت) رو انجام بدیم. فقط اگه در نهایت به حالتی که در شکل (1) زیر نشون دادم رسیدیم، از هر کدوم از این دو راس یه یال قرمز انتخاب می کنیم که به دو راس مختلف وصل باشن، بعد هم بقیه ی راس ها رو جفت می کنیم و عملیات رو انجام می دیم تا شکل (2) حاصل بشه و بعد طبق چیزی که در شکل (3) نشون دادم، دو بار دیگر نیز این عملیات رو انجام می دیم.

حالا در ادامه استقرا می زنیم و ثابت می کنیم که به ازای هر n ای، حکم سوال برقرار است:

پایه ی استقرا، n=1 که واضحه دیگههه!

فرض استقرا: حکم برای k درست است.

گام استقرا: حکم را برای k+1 نتیجه می گیریم. طبق لم 1، دو راس A و B وجود دارن که تعداد یالهای آبی متصل بهشون برابره. طبق لم 2 هم می شه کاری کرد که تمام یالهای متصل به این دو راس (نه لزوما یال بین A و B) قرمز بشن. حالا تو گراف 2k راسی (همه ی رئوس به غیر از A و B) طبق فرض استقرا می تونیم تعدادی عملیات انجام بدیم و بعد طوری اونها رو در دو دسته تقسیم کنیم که تمام یالهای بین رئوس یک دسته، قرمز باشن. فقط هر بار که خواستیم عملیات رو طبق فرض استقرا انجام بدیم، یال بین A و B رو هم انتخاب می کنیم (چون ما باید در مجموع k+1 یال انتخاب کنیم که هیچ دوتایی راس مشترک ندارن؛ ولی در گراف 2k راسی، ما k راس انتخاب کردیم که رئوس A و B هیچ سر این یالها نیستن؛ پس اگه هربار، یال بین A و B رو هم انتخاب کنیم مشکل حل می شه). خب، بعد از این هم راس A رو در دسته ی اول و راس B رو در دسته ی دوم قرار می دیم و چون یالهای بین هر کدوم از رئوس A و B با 2k راس دیگه قرمز بوده و یالهای بین هر دو راس در یک دسته از اون 2k راس دیگه هم قرمز بوده، پس در نهایت هر دو راسی که در یک دسته هستن، یال بینشون قرمزه و حکم برای k+1 هم اثبات می شه...