ماراتن ترکیبیات
پاسخ : ماراتن ترکیبیات
(با اجازه از استاد ماهان) یه سوال که من خیلی دوستش دارم اینه: گرافی چندگانه و n راسی داده شده است به طوری که هر زیرگراف k راسی آن که k حداقل 1 و حداکثر n است, حداکثر 2k-2 یال دارد. ثابت کنید می توان یال های این گراف را با دو رنگ رنگ کرد به طوری که در هر دور هر دو رنگ ظاهر شوند.
(با اجازه از استاد ماهان) یه سوال که من خیلی دوستش دارم اینه: گرافی چندگانه و n راسی داده شده است به طوری که هر زیرگراف k راسی آن که k حداقل 1 و حداکثر n است, حداکثر 2k-2 یال دارد. ثابت کنید می توان یال های این گراف را با دو رنگ رنگ کرد به طوری که در هر دور هر دو رنگ ظاهر شوند.
آخرین ویرایش توسط مدیر
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
پاسخ : ماراتن ترکیبیات
اول ثابت میکنیم گراف ساده و چند گانه در این مسئله معادلند چون توقه نداریم و اگه بیش از یک یال بین دو راس بود میتونیم هر کدومو به یک رنگ متفاوت در بیاریم و به راحتی با انجام این کار میشه به نتیجه ی بالا رسید حالا استقرا میزنیم داریم یه راس هست که درجش حداکثر 3 باشه پس اگه بخواد تو دوری بیاد ما میتونیم این دو یال رو به دو رنگ 1و2 در بیاریم پس دورمون شرط رو داره واسه بقیه ی رئوس هم استقرا میزنیم.
این قند خون هم تاثیراتی داره ها بقیش رو یادم رفت بنویسم :
ما میتونیم گراف n_1 راسی رو که روش استقرا زدیم رو رنگ تمام یال هاش رو تغییر بدیم 1به2 و 2 به 1 از این نکته هم استقاده میشه.
اول ثابت میکنیم گراف ساده و چند گانه در این مسئله معادلند چون توقه نداریم و اگه بیش از یک یال بین دو راس بود میتونیم هر کدومو به یک رنگ متفاوت در بیاریم و به راحتی با انجام این کار میشه به نتیجه ی بالا رسید حالا استقرا میزنیم داریم یه راس هست که درجش حداکثر 3 باشه پس اگه بخواد تو دوری بیاد ما میتونیم این دو یال رو به دو رنگ 1و2 در بیاریم پس دورمون شرط رو داره واسه بقیه ی رئوس هم استقرا میزنیم.
این قند خون هم تاثیراتی داره ها بقیش رو یادم رفت بنویسم :
ما میتونیم گراف n_1 راسی رو که روش استقرا زدیم رو رنگ تمام یال هاش رو تغییر بدیم 1به2 و 2 به 1 از این نکته هم استقاده میشه.
آخرین ویرایش توسط مدیر
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
پاسخ : ماراتن ترکیبیات
ای بابا دعا میکنم این یکی درست باشه :
طبق اصل لانه کبوتری یک راس وجود دارد که حداکثر 3 یال داشته باشد آن راس و یال هایش را از گراف حذف میکنیم و استقرا میزنیم حالا می خواهیم راس مذکور و یال هایش را وارد گراف کنیم دو حالت داریم یا سه یال به سه راس جدا گانه رفته اند:
به راحتی میتوان گفت دو تا از آن سه راس هستند که در گراف ساخته شده به روش استقرایی حد اقل یکی از مسیر های به طور کامل به رنگ 1 و به طور کامل به رنگ 2 را نداشته باشد بنا بر این میتوان سه یال را رنگ کرد
حالت 2 دو تا از یال ها به یک راس بروند رئوسی که به آنها میوند را 1و2 مینامیم برای این که نتوانیم چنین کاری را انجام دهیم باید دو مسیر تک با دو رنگ متفاوت بین 1و 2 وجود داشته باشد برای این که نتوانیم هیچ یک از یال های یکی از اون مسیر ها رو حذف کنیم باید برای هر کدوم از یال های یکی از اون مسیر ها یه مسیر دیگه از رنگ مخالفش وجود داشته باشه حالا اگه همه ی این مسیر ها رو پشت سر هم بذاریم (این یه تیکش یکم بازی کردن هم داره به خاطر اشتراک مسیرها)یه دور از یه رنگ به وجود میاد که تناقض هست.
ای بابا دعا میکنم این یکی درست باشه :
طبق اصل لانه کبوتری یک راس وجود دارد که حداکثر 3 یال داشته باشد آن راس و یال هایش را از گراف حذف میکنیم و استقرا میزنیم حالا می خواهیم راس مذکور و یال هایش را وارد گراف کنیم دو حالت داریم یا سه یال به سه راس جدا گانه رفته اند:
به راحتی میتوان گفت دو تا از آن سه راس هستند که در گراف ساخته شده به روش استقرایی حد اقل یکی از مسیر های به طور کامل به رنگ 1 و به طور کامل به رنگ 2 را نداشته باشد بنا بر این میتوان سه یال را رنگ کرد
حالت 2 دو تا از یال ها به یک راس بروند رئوسی که به آنها میوند را 1و2 مینامیم برای این که نتوانیم چنین کاری را انجام دهیم باید دو مسیر تک با دو رنگ متفاوت بین 1و 2 وجود داشته باشد برای این که نتوانیم هیچ یک از یال های یکی از اون مسیر ها رو حذف کنیم باید برای هر کدوم از یال های یکی از اون مسیر ها یه مسیر دیگه از رنگ مخالفش وجود داشته باشه حالا اگه همه ی این مسیر ها رو پشت سر هم بذاریم (این یه تیکش یکم بازی کردن هم داره به خاطر اشتراک مسیرها)یه دور از یه رنگ به وجود میاد که تناقض هست.
پاسخ : ماراتن ترکیبیات
من خیلی خنگم!!! ولی مثلا فرض کن اون راسی که میخوای بیاریش تو به سه تا راس مثل 1و2و3 وصل باشه. فرض کن بین راسای 1و2 هم یه مسیر آبی هست هم یه مسیر قرمز, بین راسای 2و3 یه مسیر آبی و بین راسای 3و1 یه مسیر قرمز, هیچ کدوم از این مسیرها هم با هم اشتراک ندارن. حالا اینو چجوری رنگ می کنی؟
من خیلی خنگم!!! ولی مثلا فرض کن اون راسی که میخوای بیاریش تو به سه تا راس مثل 1و2و3 وصل باشه. فرض کن بین راسای 1و2 هم یه مسیر آبی هست هم یه مسیر قرمز, بین راسای 2و3 یه مسیر آبی و بین راسای 3و1 یه مسیر قرمز, هیچ کدوم از این مسیرها هم با هم اشتراک ندارن. حالا اینو چجوری رنگ می کنی؟
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
پاسخ : ماراتن ترکیبیات
استاد شکست نفسی می فرمایید
این مثالی که زدید در حقیقت بین هر دو راسی از مثالتون دو مسیر تک رنگ وجود داره اما این حالت هم مشابه حالت دو میشه گفت چرا رده: در حقیقت یک یال رو میشه تغییر رنگ داد بدون این که به کلیت مسئله لطمه وارد بشه.
اگه بخوایم کلی بگیم:اگه بین 1و2 دو مسیر تک رنگ با رنگ های متفاوت داشته باشیم
بین یک و دو اگه مسیر آبی رو در نظر بگیریم میبینیم که بین هر دو راسی که شامل یالی از اون هستند باید یک مسیر تک رنگ از رنگ قرمز باشه چون در غیر این صورت میشه اون یال رو تغییر رنگ داد حالا میتونیم یه مسیر قرمز دیگه بین 1و2 پیدا کنیم(با کنار هم گذاشتن اون مسیر های پیدا شده همون طور که در بالا گفتم باید یکم باهاشون بازی کنیم نوشتنش یکم سخته!) که تناقض داره پس حداقل یکی از اونا رو میشه تغییر رنگ داد.
استاد شکست نفسی می فرمایید
این مثالی که زدید در حقیقت بین هر دو راسی از مثالتون دو مسیر تک رنگ وجود داره اما این حالت هم مشابه حالت دو میشه گفت چرا رده: در حقیقت یک یال رو میشه تغییر رنگ داد بدون این که به کلیت مسئله لطمه وارد بشه.
اگه بخوایم کلی بگیم:اگه بین 1و2 دو مسیر تک رنگ با رنگ های متفاوت داشته باشیم
بین یک و دو اگه مسیر آبی رو در نظر بگیریم میبینیم که بین هر دو راسی که شامل یالی از اون هستند باید یک مسیر تک رنگ از رنگ قرمز باشه چون در غیر این صورت میشه اون یال رو تغییر رنگ داد حالا میتونیم یه مسیر قرمز دیگه بین 1و2 پیدا کنیم(با کنار هم گذاشتن اون مسیر های پیدا شده همون طور که در بالا گفتم باید یکم باهاشون بازی کنیم نوشتنش یکم سخته!) که تناقض داره پس حداقل یکی از اونا رو میشه تغییر رنگ داد.
پاسخ : ماراتن ترکیبیات
یه جور خوشگل تر هم میشد اینو گفت. میشه ثابت کرد حداقل دوتا از راس های 1و2و3 هستن که هیچ زیرگرافی که شامل اون دوتا راس باشه بحرانی نیست (یه زیرگراف k راسیو میگیم بحرانی اگه حداکثر تعداد یال های ممکن یعنی 2k-2 رو داشته باشه.) پس یه یال فرضی بین اون دوتا راس می کشیم و بعد فرض استقرا. حالا اون دوتا یال که به این یال فرضی وصلن رو به رنگ همین یال فرضی می کنیم, اون یکی یال رو هم با یه رنگ دیگه!!!
یه جور خوشگل تر هم میشد اینو گفت. میشه ثابت کرد حداقل دوتا از راس های 1و2و3 هستن که هیچ زیرگرافی که شامل اون دوتا راس باشه بحرانی نیست (یه زیرگراف k راسیو میگیم بحرانی اگه حداکثر تعداد یال های ممکن یعنی 2k-2 رو داشته باشه.) پس یه یال فرضی بین اون دوتا راس می کشیم و بعد فرض استقرا. حالا اون دوتا یال که به این یال فرضی وصلن رو به رنگ همین یال فرضی می کنیم, اون یکی یال رو هم با یه رنگ دیگه!!!
پاسخ : ماراتن ترکیبیات
خب
منم بعد عمر ی اومدم
می خوام اثباتم رو بذارم که ببینید درسته یا نه:
خب استقرا می زنیم
حکم به ازای n=2
درسته
فرض کنیم که واسه n<=k
هم درسته می خوایم واسه n=k+1
اثبات کنیم
خب گراف رو در نظرمی کیریم
خب یه راس ور می داریم که به حداقل دو تا راس متمایز یال داشته باشه
****************************
اگه چنین راسی نباشه
یا رئوس گراف بعضیاشون تنهان
یا فقط یه یال دارن
یا جفت جفت با دویال بهم وصلن
که در این حالات مسئله حله
****************************
خب اگه گراف نا همبند باشه باز هر مولفه چون تو فرض استقرا می یوفته
مسئله حل می شه
پس فرض کنیم گراف همبنده
خب حالا از اون راسی که اول گفته شد شروع به پیمایش گراف می کنیم به صورت کاملا کیلویی و از رو ی یال ها به طوری که به راس تکراری نریم (DFS میزنیم)
خب به یه زیردرخت فراگیر از درخت می رسیم
حالا این درخت این خاصیت رو داره که هیچ دو راسی که تو دوتا شا خه از گراف هستن (هر شاخه از اولین راس نشئت می گیره .شاخه های تو خود شاخه اصلییا مهم نی)
تو گراف اصلی بهم وصل نیستن
چون از هر راس به تمام همسایه های دیده نشده اش می ریم پس غیر راس اول همسایه های هر راس تو شاخه خود اون راس است
حالا اگه یه راسی باشه که به این راسی که ماتوشیم وصل باشه ولی قبلا دیده شده باشه و ما از اون به این راس حاضر نیمده باشیم
یعنی این که این دو تا راس تویه شاخه نیستن
در حالی که می دونیم وقتی به یه راسی میرسیم تمام همسایه هاش رو میبینم
پس این حالت به وجود نمیاد
این همه حرف زدم که بگم دور ها تو گراف فقط تو هر شاخه هستن
و دوری نداریم که از دو یا بیشتر شاخه استفاده کنه
حالا یکی از شاخه هارو میگیرم چون اون شرط تعداد یال هارو داره پس اگه با یال های نداشتش در نظرش بگیریم بدون بقیه گراف تو فرض استقرا صدق می کنه
و بقیه گراف هم به همین صورت تو فرض استقرا صدق می کنه
پس حکم اثبات میشه
خب
منم بعد عمر ی اومدم
می خوام اثباتم رو بذارم که ببینید درسته یا نه:
خب استقرا می زنیم
حکم به ازای n=2
درسته
فرض کنیم که واسه n<=k
هم درسته می خوایم واسه n=k+1
اثبات کنیم
خب گراف رو در نظرمی کیریم
خب یه راس ور می داریم که به حداقل دو تا راس متمایز یال داشته باشه
****************************
اگه چنین راسی نباشه
یا رئوس گراف بعضیاشون تنهان
یا فقط یه یال دارن
یا جفت جفت با دویال بهم وصلن
که در این حالات مسئله حله
****************************
خب اگه گراف نا همبند باشه باز هر مولفه چون تو فرض استقرا می یوفته
مسئله حل می شه
پس فرض کنیم گراف همبنده
خب حالا از اون راسی که اول گفته شد شروع به پیمایش گراف می کنیم به صورت کاملا کیلویی و از رو ی یال ها به طوری که به راس تکراری نریم (DFS میزنیم)
خب به یه زیردرخت فراگیر از درخت می رسیم
حالا این درخت این خاصیت رو داره که هیچ دو راسی که تو دوتا شا خه از گراف هستن (هر شاخه از اولین راس نشئت می گیره .شاخه های تو خود شاخه اصلییا مهم نی)
تو گراف اصلی بهم وصل نیستن
چون از هر راس به تمام همسایه های دیده نشده اش می ریم پس غیر راس اول همسایه های هر راس تو شاخه خود اون راس است
حالا اگه یه راسی باشه که به این راسی که ماتوشیم وصل باشه ولی قبلا دیده شده باشه و ما از اون به این راس حاضر نیمده باشیم
یعنی این که این دو تا راس تویه شاخه نیستن
در حالی که می دونیم وقتی به یه راسی میرسیم تمام همسایه هاش رو میبینم
پس این حالت به وجود نمیاد
این همه حرف زدم که بگم دور ها تو گراف فقط تو هر شاخه هستن
و دوری نداریم که از دو یا بیشتر شاخه استفاده کنه
حالا یکی از شاخه هارو میگیرم چون اون شرط تعداد یال هارو داره پس اگه با یال های نداشتش در نظرش بگیریم بدون بقیه گراف تو فرض استقرا صدق می کنه
و بقیه گراف هم به همین صورت تو فرض استقرا صدق می کنه
پس حکم اثبات میشه