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