Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
Версия от 20:01, 23 февраля 2012; 194.85.161.2 (обсуждение)
Содержание
Определения
Минимальное вершинное покрытие
Определение:
Вершинным покрытием (англ. Vertex covering, VC) графа
называется такое подмножество множества вершин графа , что любое ребро этого графа инцидентно хотя бы одной вершине из множества .
Определение:
Минимальным вершинным покрытием (англ. Minimum vertex covering, MVC) графа
называется вершинное покрытие, состоящее из наименьшего числа вершин.
Пример
Множество вершин красного цвета — минимальное вершинное покрытие.
Связь MM и MVC в двудольном графе
Теорема о мощности MVC и MM
Теорема: |
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия. |
Доказательство: |
Пусть в обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода. Тогда , , где — правая и левая доли соответственно, — вершины правой и левой доли, посещенные обходом, — не посещенные обходом вершины. Тогда в могут быть следующие ребра: построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания — так, чтобы они шли из левой доли в правую. Запустим
Очевидно, что ребер из в и из из в быть не может. Ребер из из в быть не может, т.к. если такое ребро существует, то оно — ребро паросочетания. Тогда вершина насыщена паросочетанием. Но т.к. , то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро . Но тогда инцидентны два ребра из паросочетания. Противоречие.Заметим, что минимальным вершинным покрытием Тогда является либо , либо , либо . В не насыщенных паросочетанием вершин быть не может, т.к. иначе в существует дополняющая цепь, что противоречит максимальности построенного паросочетания. В свободных вершин быть не может, т.к. все они должны находиться в . Тогда т.к. ребер из паросочетания между и нет, то каждому ребру максимальным паросочетания инцидентна ровно одна вершина из . . Множество вершин является минимальным вершинным покрытием. Значит максимальное паросочетание равно минимальному вершинному покрытию. |
Алгоритм построения минимального вершинного покрытия
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
- Построить максимальное паросочетание.
- Ориентировать ребра:
- Из паросочетания — из правой доли в левую.
- Не из паросочетания — из левой доли в правую.
- Запустить обход в глубину из всех свободных вершин левой доли, построить множества .
- В качестве результата взять .
См. также
Связь вершинного покрытия и независимого множества.
Источники
1. Теорема Кёнига.