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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
  
 
===Минимальное вершинное покрытие===
 
===Минимальное вершинное покрытие===
[[Файл:Cover.jpg|thumb|right|150x150px|Пример минимального вершинного покрытия графа]]
 
 
{{Определение|neat=neat|definition=
 
{{Определение|neat=neat|definition=
 
'''Вершинным покрытием''' (англ. '''Vertex covering''', '''VC''') графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>.
 
'''Вершинным покрытием''' (англ. '''Vertex covering''', '''VC''') графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>.
Строка 13: Строка 12:
 
'''Минимальным вершинным покрытием''' (англ. '''Minimum vertex covering''', '''MVC''') графа <tex>G=(V,E)</tex> называется вершинное покрытие, состоящее из наименьшего числа вершин.  
 
'''Минимальным вершинным покрытием''' (англ. '''Minimum vertex covering''', '''MVC''') графа <tex>G=(V,E)</tex> называется вершинное покрытие, состоящее из наименьшего числа вершин.  
 
}}
 
}}
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
 +
<br/>
  
<br/><br/>
+
==Пример==
 +
[[Файл:Cover.jpg|300px]]
 +
<br/>
 +
Множество вершин красного цвета - минимальное вершинное покрытие.
 +
<br/>
  
 
<br/>
 
<br/>
Строка 27: Строка 35:
 
Тогда <tex>L = L^+ \cup L^-</tex>, <tex>R = R^+ \cup R^-</tex>, где <tex>L, R</tex> &ndash; правая и левая доли соответственно, <tex>L^+, R^+</tex> &ndash; вершины правой и левой доли, посещенные обходом, <tex>L^-, R^-</tex> &ndash; не посещенные обходом вершины.
 
Тогда <tex>L = L^+ \cup L^-</tex>, <tex>R = R^+ \cup R^-</tex>, где <tex>L, R</tex> &ndash; правая и левая доли соответственно, <tex>L^+, R^+</tex> &ndash; вершины правой и левой доли, посещенные обходом, <tex>L^-, R^-</tex> &ndash; не посещенные обходом вершины.
 
Тогда в <tex>G</tex> могут быть следующие ребра:
 
Тогда в <tex>G</tex> могут быть следующие ребра:
[[Файл:bipartdfs_right.jpg|thumb|right|240x240px|Доли <tex>L^+, L^-, R^+, R^-</tex> и ребра между ними.]]
+
[[Файл:bipartdfs_right.jpg|thumb|center|300px|Доли <tex>L^+, L^-, R^+, R^-</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>R^-</tex> в вершины <tex>L^-</tex>.  
 
*Из вершин <tex>L^-</tex> в вершины <tex>R^-</tex> и из вершин <tex>R^-</tex> в вершины <tex>L^-</tex>.  

Версия 02:37, 18 января 2012

Определения

Максимальное паросочетание

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


Минимальное вершинное покрытие

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


Определение:
Минимальным вершинным покрытием (англ. Minimum vertex covering, MVC) графа [math]G=(V,E)[/math] называется вершинное покрытие, состоящее из наименьшего числа вершин.






Пример

Cover.jpg
Множество вершин красного цвета - минимальное вершинное покрытие.



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

Теорема о мощности MVC и MM

Теорема:
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
Доказательство:
[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^+, L^-, R^+, R^-[/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]L^- \cup R^+[/math] и [math]|MVC| = |MM|[/math].
[math]\triangleleft[/math]

Алгоритм построения MVC

Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:

  • Построить максимальное паросочетание.
  • Ориентировать ребра:
    • Из паросочетания – из правой доли в левую.
    • Не из паросочетания – из левой доли в правую.
  • Запустить обход в глубину из всех свободных вершин левой доли, построить множества [math]L^+,L^-,R^+,R^-,[/math].
  • В качестве результата взять [math]L^- \cup R^+[/math].

Источники

1. Теорема Кёнига.