مجموعهٔ یال های یک گرافِ بدون گرهٔ درجه فرد را میتوان به شکل اجتماع مجموعه یال های دورهای مجزایی از آن نوشت.

Question

نشان دهید که اگر $G$ هیچ گرهٔ با درجهٔ فردی نداشته‌باشد، آنگاه دورهای یال-مجزایِ $C_1$، $C_2$، ...، $C_m$ای وجود دارند که $$E(G)=E(C_1)\cup E(C_2)\cup\cdots\cup E(C_m)$$

Comments

@zey_nab این پست را در مورد نحوهٔ مرجع‌دهی درست بخوانید https://math.irancircle.com/11973/#a16525 به عنوان فردی دانشگاهی انتظار می‌رود که بتوانید مرجع‌دهی را درست انجام بدهید، اگر در تحقیقی اینگونه مرجع را بنویسید آن را در هیچ مجله‌ای نمی‌پذیرند. نام کتابی که منظورتان است Graph theory with applications است. اگر به فارسی ترجمه و چاپ شده‌است همان نام چاپ‌شده‌اش را بنویسید. اگر نسخهٔ زبان اصل آن منظورتان است که باید به همین نام چاپ‌شده‌ای که اشاره کردم بنویسید. بعلاوه ترجمهٔ این عبارت «نظریه‌های گراف» نمی‌شود، کدام چند نظریه؟ ترجمهٔ صحیح این می‌شود: «نظریهٔ گراف به همراه کاربردها». نام نویسنده‌ها را هم به زبانی که در کتاب دیده‌اید بنویسید. بعلاوه آقای مورتی چند کتاب دارد که در عنوانشان «نظریهٔ گراف» آورده‌شده‌است مانند کتابی که عنوانش Graph Theory -ِ خالی است.

اگر در مورد تلاش خودتان یا اینکه چه چیزی فکر کرده‌اید و به مشکل خورده‌ای یا چه چیزی را متوجه نمی‌شوید هم توضیح دهید آنگاه پاسخی که دریافت خواهیدکرد به گونه‌ای خواهد بود که دقیقا مشکل شما را رفع می‌کند و برایتان آموزنده‌تر است.

---

سلام. فکر میکردم اینجا صرفا یه انجمن گفتگو محوره که خیلی ارجاع سوالات اهمیت نداره برای همین سرسری اون قسمت رو پر کردم. درسته که خیلی خوب نمیتونم بعضی تمرینات کتاب ها رو حل کنم اما به خوبی میتونم ارجاع دهی ها رو انجام بدم:) در کل ممنون از تذکرتون و اصلاح.

Answer 1

گراف زوج G با e یال مفروض است؛ با استفاده از اصل استقرای قوی به حل تمرین می-پردازیم. پایه استقرا: حکم را برای گراف بدیهی ( گرافی که فقط یک راس دارد) بررسی میکنیم. گراف بدیهی شرط مسئله را دارد (درجه آن زوج است) و دارای کمترین تعداد یال است. پس حکم استقرا برای پایه استقرا برقرار است. فرض استقرا: فرض میکنیم حکم برای همه گرافهای زوج که تعداد یالهایشان کمتر از e است برقرار باشد. حکم استقرا: گراف زوج e یالی داریم، نشان میدهیم که میتوان یالهای آن را به شکل اجتماع مجموعه یالهای دورهای یال- مجزا نوشت (افراز کرد). از راس دلخواه v_{1} شروع میکنیم و مسیری را میپیماییم، از آنجایی که درجات گراف زوج است و گراف متناهی به هر راسی که وارد میشویم یالی وجود دارد که از طرف دیگر خارج شویم؛ جایی به راسی تکراری میرسیم و دوری تشکیل میشود، این دور را c_{1} مینامیم: C {1} : v{1} e_{1} v_{2} e_{2}…v_{k} e v_{1} اگر این دور شامل همه ی یالهای گراف باشد، اثبات تمام و حکم برقرار است؛ در غیر اینصورت، دور c_{1} را از گراف حذف میکنیم. تعداد یالهای باقی مانده از e کمتر است و درجات همه ی راسها زوج میباشد (از راسهایی که در مسیر دور قرار دارند دو یال حذف شده پس درجه ی همه ی راسها زوج است)، پس شرایط فرض برقرار است و مجموعه ی یالهای این گراف را میتوان به صورت اجتماع مجموعه یالهای دورهای یال-مجزای گراف نوشت.