Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
Версия от 01:27, 9 декабря 2010; Alexey.tsyplenkov (обсуждение | вклад)
Определения
Определение: |
Паросочетанием | в графе называется такое подмножество множества ребер графа , что каждая вершина инцидентна не более чем одному ребру из .
Определение: |
Максимальным паросочетанием | в графе называется паросочетание максимальной мощности.
Определение: |
Вершинным покрытием | графа называется такое подмножество множества вершин графа , что каждому ребру инцидентна хотя бы одна вершина из .
Определение: |
Минимальным вершинным покрытием | графа называется вершинное покрытие минимальной мощности.