سلام میگم یک سر به سایت www.fanavard.ir بزنید. مسابقات برنامه نویسی شون شروع شده. گواهی رسمی از طرف دانشگاه شریف می ده. 50 تا سکه هم جایزشه
2016-10-26 08:49:38 -0600 امیر شکریآمار پرسش:
- پرسیده شده: 2016-03-30 02:45:34 -0600
- مشاهده شده: 292 بار
- بروز شده: 2016-04-07 13:55:27 -0600
پرسش‌های مشابه:
بازی بازی با گراف خسته و سرحال
اثبات یک قضیه در مورد قطر گراف
مشکل در حل سوالات الگوریتم های داینامیک
پیمایش صعودی یال های خوشه وزندار
BFS رو چجوری بزنم که تایم نیشه؟!؟!؟!؟!؟!؟!؟!؟!؟!؟
مربع یک رنگ در صفحه ی دو رنگ !
سوال چهار مرحله دوم امروز !!!!!!
sgu 502 راه حل با اوردر وحشتناک و ac!
20 تنیس باز، 14 بازی انجام می دهند. یک تطابق با 6 یال وجود دارد؟
رنک آمیزی یک 12ضلعی منتظم با شرط خاص!
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
الگوریتـــــــــــــــــــــــــم....
۱.الگوریتمی از O(neΔ)O(neΔ) ارایه دهید که یال‌های یک گراف ساده با nn راس و ee یال را با ΔΔ رنگ رنگ‌آمیزی یالی سره کند.
۲.گراف GG با ee یال که دور زوج ندارد را در نظر بگیرید. الگوریتمی از O(e)O(e) ارائه دهید که این گراف را با ۳ رنگ رنگ‌آمیزی معتبر راسی کند.؟
2016-03-30 02:45:34 -0600
پروفسور یزدانی 109 ● 1 ● 2 ● 6
نظرات
1 پاسخ
برای دومی درخت bfs رو در نظر بگیر.و اول همه رو با دوتا رنگ رنگشون کن.
حالا یال های دور فرد ساز مه بین طبقه ها هستن رو اضافه کن.حالا دوتا چیز داریم.
1-هیچ دوتا دور فرد اشتراک یالی ندارند پس وقتی یه یال میزاریم بین رئوس تا lcaشون اون بالا دیگه نمیشه یالی اضافه کرد و مشکلی به وجود نمی آید.
2-وقتی یال هارو میزاریم بین خود همین یال ها توی طبقات دور بوجود نمی آد(حتی فرد) که راحت میشه اثبات کرد.
پس تو هر طبقه یه سری مسیر داریم.خب حالا راس های مسیر هارو یکی در میون به رنگ سوم کنین.
امیدوارم جوب نزده باشم...
2016-04-07 13:55:27 -0600
تنیسون 948 ● 3 ● 9 ● 18