Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
Версия от 17:38, 15 декабря 2010; Alexey.tsyplenkov (обсуждение | вклад)
Определения
Максимальное паросочетание
Определение: |
Паросочетанием | в графе называется такое подмножество множества ребер графа , что каждая вершина инцидентна не более чем одному ребру из .
Определение: |
Максимальным паросочетанием | в графе называется паросочетание максимальной мощности.
Минимальное вершинное покрытие
Определение: |
Вершинным покрытием | графа называется такое подмножество множества вершин графа , что каждому ребру инцидентна хотя бы одна вершина из .
Определение: |
Минимальным вершинным покрытием | графа называется вершинное покрытие минимальной мощности.
Связь MM и MVC в двудольном графе
Теорема о мощности MVC и MM
Теорема: |
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
Доказательство: |
Пусть в построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания – так, чтобы они шли из левой доли в правую. Запустим обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода. Тогда , , где – правая и левая доли соответственно, – вершины правой и левой доли, посещенные обходом, – не посещенные обходом вершины. Тогда в могут быть следующие ребра:
Очевидно, что ребер из в и из из в быть не может. Ребер из из в быть не может, т.к. если такое ребро существует, то оно – ребро паросочетания. Тогда вершина насыщена паросочетанием. Но т.к. , то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро . Но тогда инцидентны два ребра из паросочетания. Противоречие.Заметим, что минимальным вершинным покрытием Тогда является либо , либо , либо . В не насыщенных паросочетанием вершин быть не может, т.к. иначе в существует дополняющая цепь, что противоречит максимальности построенного паросочетания. В свободных вершин быть не может, т.к. все они должны находиться в . Тогда т.к. ребер из паросочетания между и нет, то каждому ребру инцидентна ровно одна вершина из . . Значит, . |
Алгоритм построения MVC
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
- Построить максимальное паросочетание.
- Ориентировать ребра:
- Из паросочетания – из правой доли в левую.
- Не из паросочетания – из левой доли в правую.
- Запустить обход в глубину из всех свободных вершин левой доли, построить множества .
- В качестве результата взять .