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