ماراتن گراف
- ارسال ها
- 6
- لایک ها
- 3
- امتیاز
- 3
پاسخ : ماراتن گراف
اگر k زوج باشد سوال بدیهی است . اگر k فرد باشد آنگاه میتوان با دوگونه شماردن یال های یک مولفه همبندی به تناقض رسید البته زوجیت k در این دو گونه شمردن اثری ندارد .
ببخشید یک سوال داشتم میخواستم بدونم که من هر موقع سوالی از این مراتن را حل کردم که کسی هنوز حل آن را ننوشته بود میتوانم حل خود را بنویسم یا خیر ؟
ممنون
اگر k زوج باشد سوال بدیهی است . اگر k فرد باشد آنگاه میتوان با دوگونه شماردن یال های یک مولفه همبندی به تناقض رسید البته زوجیت k در این دو گونه شمردن اثری ندارد .
ببخشید یک سوال داشتم میخواستم بدونم که من هر موقع سوالی از این مراتن را حل کردم که کسی هنوز حل آن را ننوشته بود میتوانم حل خود را بنویسم یا خیر ؟
ممنون
پاسخ : ماراتن گراف
:218:
برای همه n های غیر 4 میشه برای اثباتشم به وضوح برای فردها درسته برای زوجاشم دو راس که درجه شون برابره و همسایه هاشون بقیه گرافو افراز کردنو در نظر می گیریم(حتما چنین چیزی وجود داره چون دو راس با درجه برابر داریم) و روی n استقرا میزنیم(از n به n+2) فقط باید برای 6 چک کنیم که اونم بدیهیه:3:
:218:
- ارسال ها
- 199
- لایک ها
- 268
- امتیاز
- 0
پاسخ : ماراتن گراف
درسته مجتبی. 3n/2-1 یال بود که من اشتباه نوشتم. راهت هم دست است. البته راه های ساده تری هم وجود دارد. مثلا برای قسمت الف می توانیم از این استفاده کنیم که هر گراف ساده یک زیر گراف دو بخشی با حداقل نصف یال ها دارد( خود این لم هم تمرین قشنگی است و اگر خواستید می توانید بعدا آن را هم حل کنید). همچنین برای قسمت ب می توانیم با استفاده از طولانی ترین مسیر و استقرا به راحتی مسئله را حل کنیم. همچنین به عنوان یک تمرین خوب می توانید روی این هم کار کنید که کران گفته شده در قسمت ب بهترین است.
حالا مجتبی سوال بعدی را بگذار
درسته مجتبی. 3n/2-1 یال بود که من اشتباه نوشتم. راهت هم دست است. البته راه های ساده تری هم وجود دارد. مثلا برای قسمت الف می توانیم از این استفاده کنیم که هر گراف ساده یک زیر گراف دو بخشی با حداقل نصف یال ها دارد( خود این لم هم تمرین قشنگی است و اگر خواستید می توانید بعدا آن را هم حل کنید). همچنین برای قسمت ب می توانیم با استفاده از طولانی ترین مسیر و استقرا به راحتی مسئله را حل کنیم. همچنین به عنوان یک تمرین خوب می توانید روی این هم کار کنید که کران گفته شده در قسمت ب بهترین است.
حالا مجتبی سوال بعدی را بگذار
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
پاسخ : ماراتن گراف
یه دونه دیگه هم پیدا کردم که ایده حلش کپی همیناست
http://www.irysc.com/forum/t3598/
یه دونه دیگه هم پیدا کردم که ایده حلش کپی همیناست
http://www.irysc.com/forum/t3598/
- ارسال ها
- 362
- لایک ها
- 74
- امتیاز
- 28
پاسخ : ماراتن گراف
راستی برای اطلاعات بیشتر بچس اون سوال روسیه: اگه یه گراف دو همبند باشه میشه یه راس و تمام یال های متصل بهش رو حذف کرد به طوری که گراف همچنان دو همبند بمونه با این لم میشه تقریبا تمام سواللات دو همبندی رو له کرد .برای kهمبندی هم حکم درسته یعنی میشه یه راس رو حذف کرد به طوری که همچنان k همبندبمونه.
راستی برای اطلاعات بیشتر بچس اون سوال روسیه: اگه یه گراف دو همبند باشه میشه یه راس و تمام یال های متصل بهش رو حذف کرد به طوری که گراف همچنان دو همبند بمونه با این لم میشه تقریبا تمام سواللات دو همبندی رو له کرد .برای kهمبندی هم حکم درسته یعنی میشه یه راس رو حذف کرد به طوری که همچنان k همبندبمونه.
