قضیه کونیگ
(تغییرمسیر از نظریه کونیگ)
نظریهٔ کونیگ نشان می‌دهد که پرسمان جورسازی بیشینه و پرسمان پوشش گره‌ای کمینه برای گرافی دوبخشی هم ارز هستند.
جورسازی زیرمجموعه‌ای از یالهای گراف است که هیچ جفت-یالی در این زیرمجموعه همسایه نباشند. جورسازی بیشینه بزرگ‌ترین زیرمجموعه از یال‌هاست که یک جورسازی را می‌سازند.
پوشش گره‌ی در یک گراف مجموعه‌ای از گرههای می‌باشد که می‌بایست حداقل یک گره از همهٔ یالهای گراف در این مجموعه باشد.
بازبُردها[ویرایش]
- Wikipedia contributors, "König's theorem (graph theory)," Wikipedia, The Free Encyclopedia, (accessed March 1, 2013).