Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
 
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
 
|proof=
 
|proof=
 +
Пусть в <tex>G</tex> построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания --- так, чтобы они шли из левой доли в правую. Запустим обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода.
 +
Тогда <tex>L = L_+ \cup L_-</tex>, <tex>R = R_+ \cup R_-</tex>, где <tex>L, R</tex> --- правая и левая доли соответственно, <tex>L_+, R_+</tex> --- вершины правой и левой доли, посещенные обходом, <tex>L_-, R_-</tex> --- не посещенные обходом вершины.
 +
Тогда в <tex>G</tex> могут быть следующие ребра:
 +
*Из вершин <tex>L_+</tex> в вершины <tex>R_+</tex> и из вершин <tex>R_+</tex> в вершины <tex>L_+</tex>.
 +
*Из вершин <tex>L_-</tex> в вершины <tex>R_-</tex> и из вершин <tex>R_-</tex> в вершины <tex>L_-</tex>.
 +
*Из вершин <tex>L_-</tex> в вершины <tex>R_+</tex>.
  
 +
Очевидно, что ребер из <tex>L_+</tex> в <tex>R_-</tex> и из из <tex>R_+</tex> в <tex>L_-</tex> быть не может.
 +
Ребер из из <tex>R_-</tex> в <tex>L_+</tex> быть не может, т.к. если такое ребро <tex>uv</tex> существует, то оно --- ребро паросочетания. Тогда вершина <tex>v</tex> насыщена паросочетанием. Но т.к. <tex>v \in L_+</tex>, то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро <tex>wv, w \in R_+</tex>. Но тогда <tex>v</tex> инцидентны два ребра из паросочетания. Противоречие.
 +
 +
Заметим, что минимальным вершинным покрытием <tex>G</tex> является либо <tex>L</tex>, либо <tex>R</tex>, либо <tex>L_- \cup R_+</tex>.
 +
В <tex>R_+</tex> не насыщенных паросочетанием вершин быть не может, т.к. иначе в <tex>G</tex> существует дополняющая цепь, что противоречит максимальности построенного паросочетания.
 +
В <tex>L_-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L_+</tex>. Тогда т.к. ребер из паросочетания между <tex>R_+</tex>
 +
и <tex>L_-</tex> нет, то каждому ребру <tex>MM</tex> инцидентна ровно одна вершина из <tex>L_- \cup R_+</tex>.
 +
 +
Тогда <tex>|L_- \cup R_+| = |MM| \le min(|L|, |R|)</tex>. Значит, <tex>|MVC| = |MM|</tex>.
 
}}
 
}}
 
[[Файл:Matching.jpg|thumb|right|Пример максимального паросочетания]]
 
[[Файл:Matching.jpg|thumb|right|Пример максимального паросочетания]]

Версия 16:48, 15 декабря 2010

Определения

Определение:
Паросочетанием [math]M[/math] [math](matching)[/math] в графе [math]G[/math] называется такое подмножество множества ребер графа [math]Е[/math], что каждая вершина [math]G[/math] инцидентна
не более чем одному ребру из [math]M[/math].


Определение:
Максимальным паросочетанием [math]MM[/math] [math](maximum[/math] [math]matching)[/math] в графе [math]G[/math] называется паросочетание максимальной мощности.


Определение:
Вершинным покрытием [math]VC[/math] [math](vertex[/math] [math]covering)[/math] графа [math]G[/math] называется такое подмножество множества вершин графа [math]V[/math], что каждому ребру [math]G[/math]
инцидентна хотя бы одна вершина из [math]VC[/math].


Определение:
Минимальным вершинным покрытием [math]MVС[/math] [math](minimum[/math] [math]vertex[/math] [math]covering)[/math] графа [math]G[/math] называется вершинное покрытие минимальной мощности.


Связь MM и MVC в двудольном графе

Теорема:
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
Доказательство:
[math]\triangleright[/math]

Пусть в [math]G[/math] построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания --- так, чтобы они шли из левой доли в правую. Запустим обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода. Тогда [math]L = L_+ \cup L_-[/math], [math]R = R_+ \cup R_-[/math], где [math]L, R[/math] --- правая и левая доли соответственно, [math]L_+, R_+[/math] --- вершины правой и левой доли, посещенные обходом, [math]L_-, R_-[/math] --- не посещенные обходом вершины. Тогда в [math]G[/math] могут быть следующие ребра:

  • Из вершин [math]L_+[/math] в вершины [math]R_+[/math] и из вершин [math]R_+[/math] в вершины [math]L_+[/math].
  • Из вершин [math]L_-[/math] в вершины [math]R_-[/math] и из вершин [math]R_-[/math] в вершины [math]L_-[/math].
  • Из вершин [math]L_-[/math] в вершины [math]R_+[/math].

Очевидно, что ребер из [math]L_+[/math] в [math]R_-[/math] и из из [math]R_+[/math] в [math]L_-[/math] быть не может. Ребер из из [math]R_-[/math] в [math]L_+[/math] быть не может, т.к. если такое ребро [math]uv[/math] существует, то оно --- ребро паросочетания. Тогда вершина [math]v[/math] насыщена паросочетанием. Но т.к. [math]v \in L_+[/math], то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро [math]wv, w \in R_+[/math]. Но тогда [math]v[/math] инцидентны два ребра из паросочетания. Противоречие.

Заметим, что минимальным вершинным покрытием [math]G[/math] является либо [math]L[/math], либо [math]R[/math], либо [math]L_- \cup R_+[/math]. В [math]R_+[/math] не насыщенных паросочетанием вершин быть не может, т.к. иначе в [math]G[/math] существует дополняющая цепь, что противоречит максимальности построенного паросочетания. В [math]L_-[/math] свободных вершин быть не может, т.к. все они должны находиться в [math]L_+[/math]. Тогда т.к. ребер из паросочетания между [math]R_+[/math] и [math]L_-[/math] нет, то каждому ребру [math]MM[/math] инцидентна ровно одна вершина из [math]L_- \cup R_+[/math].

Тогда [math]|L_- \cup R_+| = |MM| \le min(|L|, |R|)[/math]. Значит, [math]|MVC| = |MM|[/math].
[math]\triangleleft[/math]
Пример максимального паросочетания