جورسازی (تطابق) در گرافهای دوبخشی

Question

فرض کنید که M و N جورسازی‌هایی در گراف دوبخشی G با بخش‌های X و Y باشند به‌طوری که $S \subseteq X $ به وسیله M و $T \subseteq Y $ به وسیله N اشباع شده باشند. ثابت کنید که G شامل یک جورسازی است که $S \cup T $ را اشباع می‌کند.

Comments

@Esmaeiliyan پست زیر پیرامون عنوان مناسب را بخوانید و سپس عنوان پرسش‌تان را ویرایش کنید، عنوان با برچسب و اسم درس فرق می‌کند. بعلاوه به تلاش خودتان نیز اشاره کنید.
https://math.irancircle.com/11973

---

سلام. عنوانی مناسب تر برای این مسئله پیدا نکردم. چرا که به دلیل محدودیت در تعداد کاراکترها، نوشتن عنوانی کامل میسر نیست. درمورد برچسب، به غیر از گراف و جورسازی برچسب دیگری نه مناسب هست و نه وجود دارد که اضافه گردد.

---

در مورد حل:
منظور از یک جورسازی، زیر مجوعه‌ای از یال‌های گراف است به طوری که هیچ راس مشترکی نداشته باشند. فرض کنید M  یک جورسازی از گراف G باشد. گوییم راس v از گراف G توسط M اشباع شده است هرگاه یالی از M موجود باشد که v یکی از دو انتهای آن یال باشد.
برای اثبات F را اجتماع یال‌های M و N (مطابق فرض مسئله) در نظر گرفته و زیر گراف القایی توسط F را می‌سازم. اما برای ادامه اثبات نمیتوانم کاری از پیش ببرم.