به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
+2 امتیاز
259 بازدید
در دانشگاه توسط Zharamm (11 امتیاز)

در قضیه اینکه یک گراف دوبخشی است اگر و فقط اگر هیچ دور فردی نداشته باشد برای قسمت دوم که می‌خواهیم ثابت کنیم G یک گراف دوبخشی است میگوییم فرض میکنیم G همبند است . سوال ؟ چرا فرض میکنیم G. همبند است

از کتاب نظریه گراف باندی مورتی

مرجع: کتاب نظریه گراف باندی مورتی

1 پاسخ

+1 امتیاز
توسط Dana_Sotoudeh (2,375 امتیاز)

با سلام؛

دو حالت داریم یا گراف ناهمبند است یا همبند.

اگر ناهمبند باشد واضح است که شامل یک دور نیست و در نتیجه دوری به طول فرد ندارد.

اگر همبند باشد، مطابق آنچه که در کتاب باندی مورتی یا کتاب داگلاس بی وست گفته شده اثبات را انجام خواهید داد.

در واقع کتاب برای اینکه اثبات طولانی نشود، فرض کرده که خواننده حالت ناهمبند بودن برایش بدیهی و واضح است.

این چرخ فلک که ما در او حیرانیم<br> فانوس خیال از او مثالی دانیم<br> خورشید چراغ دان و عالم فانوس<br> ما چون صوریم کاندرو حیرانیم
...