آمار پرسش:
- پرسیده شده: 2020-05-20 06:21:57 -0500
- مشاهده شده: 140 بار
- بروز شده: 2020-05-20 07:32:59 -0500
پرسش‌های مشابه:
پیدا کردن گراف دوبخشی کامل یکرنگ
حداکثر تعداد یالهای گراف بدون مثلث
اثبات همبند بودن مکمل گراف ناهمبند
همه را با تلفن خبر کنید - دوره ی 05 - مرحله ی 1
رنگ‌آمیزی صفحه بخش‌بندی شده توسط دایره‌ها با دو رنگ
پیدا کردن مولفه های قویا همبند گراف جهت دار
انگور، آن هم از نوع «درختی» - آزمون دوم آزمایشی شاززز
نکاتی در مورد نوشتن پاسخ:
استفاده از ویرایشگر:
علائم ریاضی:
مجموعه یالهای یک گراف بدون گره فرد را میتوان به شکل اجتماع مجموعه یالهای دورهای مجزا از آن نوشت.
1 پاسخ
فرض میکنیم گراف همبنده، اگه درجه همه رئوس ۰ باشه که ما ۰ تا دور داریم پس حکم برقراره، حالا اگه یه راسی باشه که درجه‌ش ۰ نباشه، بنابر فرض تو مولفه‌ای که اون راس قرار داره، درجه هر راس بزرگ‌تر مساوی ۲ه. حالا یه راسو تو اون مولفه میگیریم و بلندترین مسیر گذرنده ازش رو در نظر میگیریم، حالا ادعا میکنیم همسایه‌های آخرین و اولین راس مسیر، توی مسیر قرار دارن، چون اگه توی مسیر قرار نداشته باشن که ما میتونیم اونارو هم در نظر بگیریم و مسیر بلندتری داشته باشیم که خلاف فرضمونه، اگه همسایه‌دیگه ای هم نداشته باشه یعنی درجه‌ش ۱ه که تناقضه. پس ادعامون هم اثبات شد و همسایه هاشون توی مسیر قرار دارن، واضحه که توی گراف دور داریم، یالهای دور رو از گراف حذف میکنیم و چون هر راس ۲ یال توی دور داره درجه‌ش منهای ۲ میشه در نتیجه زوج میمونه. اینکارو انقدر تکرار میکنیم تا به گراف تهی برسیم، iامین دوری که حذف کردیم رو اسمشو Ci میزاریم. حالا واضحه که گرافو به تعدادی دور تجزیه کردیم که اجتماعشون یالهای گراف اصلی رو می‌سازن.
