قضیه کونیگ

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

نظریهٔ کونیگ نشان می‌دهد که پرسمان جورسازی بیشینه و پرسمان پوشش گره‌ای کمینه برای گرافی دوبخشی هم ارز هستند.

جورسازی زیرمجموعه‌ای از یال‌های گراف است که هیچ جفت-یالی در این زیرمجموعه همسایه نباشند. جورسازی بیشینه بزرگ‌ترین زیرمجموعه از یال‌هاست که یک جورسازی را می‌سازند.

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

بازبُردها[ویرایش]