Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
Версия от 16:10, 15 декабря 2010; 192.168.0.2 (обсуждение)
Определения
Определение: |
Паросочетанием не более чем одному ребру из . | в графе называется такое подмножество множества ребер графа ,
что каждая вершина инцидентна
Определение: |
Максимальным паросочетанием | в графе называется паросочетание максимальной мощности.
Определение: |
Вершинным покрытием инцидентна хотя бы одна вершина из . | графа называется такое подмножество множества вершин графа , что каждому ребру
Определение: |
Минимальным вершинным покрытием | графа называется вершинное покрытие минимальной мощности.
Связь MM и MVC в двудольном графе
Теорема: |
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. |