گراف دو بخشی

[amir.ekhlasi]

ثابت کنید اگر گرافی فاقد مثلث باشد (دور سه تایی نداشته باشد) و درجه تمام رئوس آن بیشتر از 2n/5 باشد (n تعداد رئوس است) آنگاه این گراف دو بشخی است.

 

[goodarz]

پاسخ : گراف دو بخشی

دور به طول پنج چیه اونوقت؟؟

 

[goodarz]

پاسخ : گراف دو بخشی

دور به طول پنج تو شرایط سوال صدق می کنه ولی دوبخشی نیست....

 

[mandana_hashemi]

پاسخ : گراف دو بخشی

حق با اقای goodarz
هم دور به طول 5 می تونه مثال نقض باشن
مگه این که براش شرط بذارین
سوال رو از کجا اوردین؟

 

[goodarz]

پاسخ : گراف دو بخشی

البته دور به طول 4 دوبخشیه ها....:99:

 

[amir.ekhlasi]

پاسخ : گراف دو بخشی

سؤال ویرایش شد. لطفا حل کنید.

 

[mahanmath]

پاسخ : گراف دو بخشی

سؤال ویرایش شد. لطفا حل کنید.

(مثله ... خوابم میاد پس ببخشید اگه اشتبه .)

فرض کنید گراف دو بخشی نباشه . حالا ثابت می کنیم یه راس با درجه حداکثر فلان !!! وجود داره .
چون دو بخشی نیست دور فرد داره و چون مثلث نداره کوچکترین دور فرد حداقل 5 تا راس داره . حالا چون این کوچکترین دور فرد هست و گراف مثلث نداره پس هر راسه خارج این دور به حداکثر 2 تا از رئوس دور وصله .
پس مجموع درجات رئوس دور حداکثر 2n هست و طبق لانه راسی با درجه حداکثر 2n/5 داریم .... تمام :1: