گراف
- شروع کننده موضوع Devaince
- تاریخ شروع
)
erfan_ashorian
کاربر حرفه‌ای
- ارسال‌ها
- 397
- امتیاز
- 1,241
- نام مرکز سمپاد
- 2
- شهر
- تهران
- دانشگاه
- _ان شا الله قوزاباد
- رشته دانشگاه
- _علوم کامپیوتر(البته در این
پاسخ : گراف
راهنمایی » ابتدا به برهان خلف فرض کنید s>= 2n/5 باشد! سپس کوچکترین دور فرد را در نظر بگیرید(همچین دوری حتما داریم چون گراف غیر دوبخشیست) بدیهیست که توی این دور یال نداریم یعنی یالی نداریم که بین دو راس از این دور باشد چون در این صورت دور فرد کوچکتری بوجود می آید حال ثابت کنید راسی وجود دارد که به سه راس از این کوچکترین دور متصل است و . . . .
راهنمایی » ابتدا به برهان خلف فرض کنید s>= 2n/5 باشد! سپس کوچکترین دور فرد را در نظر بگیرید(همچین دوری حتما داریم چون گراف غیر دوبخشیست) بدیهیست که توی این دور یال نداریم یعنی یالی نداریم که بین دو راس از این دور باشد چون در این صورت دور فرد کوچکتری بوجود می آید حال ثابت کنید راسی وجود دارد که به سه راس از این کوچکترین دور متصل است و . . . .