نظریه کونیگ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
همانطور که در گراف دو بخشی بالا مشاهده می‌شود طبق نظریهٔ König، بیشترین تعداد جورسازی‌ها (یالهای آبی)، با کمترین تعداد پوشش راسی (راس‌های قرمز)، مساوی است و برابر ۶ می‌باشد.

نظریهٔ کونیگ برابری(هم ارزی) مسئلهٔ بیشترین تعداد جورسازی و مسئلهٔ کمترین تعداد پوشش راسی، در یک گراف دوبخشی را بیان می‌کند.

جورسازی به این صورت تعریف می‌شود که در یک گراف G(V,E)، مجموعه Mهایی که M⊆E، یک جورسازی نامند، هرگاه هیچ دو یال در M، مجاور هم نباشند.

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

منابع[ویرایش]