قضیه کونیگ
نظریهٔ کونیگ نشان می‌دهد که پرسمان جورسازی بیشینه و پرسمان پوشش گره‌ای کمینه برای گرافی دوبخشی هم ارز هستند.
در گراف دو بخشی بالا، شمار جورسازی بیشینه (یالهای آبی)، با پوشش گره‌ای بیشینه (گرههای قرمز) یکسان و برابر با ۶ است.
جورسازی زیرمجموعه‌ای از یالهای گراف است که هیچ جفت-یالی در این زیرمجموعه همسایه نباشند. جورسازی بیشینه بزرگ‌ترین زیرمجموعه از یال‌هاست که یک جورسازی را می‌سازند.
پوشش گره‌ی در یک گراف مجموعه‌ای از گرههای می‌باشد که می‌بایست حداقل یک گره از همهٔ یالهای گراف در این مجموعه باشد.
بازبُردها
- Wikipedia contributors, "König's theorem (graph theory)," Wikipedia, The Free Encyclopedia, (accessed March 1, 2013).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.