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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Минимальное вершинное покрытие)
(См. также)
(не показана 31 промежуточная версия 6 участников)
Строка 1: Строка 1:
==Определения==
+
==Минимальное вершинное покрытие==
===Максимальное паросочетание===
 
 
{{Определение|definition=
 
{{Определение|definition=
Максимальным [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|паросочетанием]] <tex>MM</tex> <tex>(maximum</tex> <tex>matching)</tex> в [[Основные_определения_теории_графов|графе]] <tex>G</tex> называется паросочетание максимальной мощности.
+
'''Вершинным покрытием''' ''(англ. vertex covering)'' графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>.
 +
}}
 +
{{Определение|definition=
 +
'''Минимальным вершинным покрытием''' ''(англ. minimum vertex covering)'' графа <tex>G=(V,E)</tex> называется вершинное покрытие, состоящее из наименьшего числа вершин.  
 
}}
 
}}
  
===Минимальное вершинное покрытие===
+
[[Файл:Cover.jpg|left|thumb|300px|Множество вершин красного цвета — минимальное вершинное покрытие.]]
[[Файл:Cover.jpg|right|100px|Пример минимального вершинного покрытия графа]]
+
<br clear="all"/>
{{Определение|neat=neat|definition=
+
===Теорема о мощности минимального вершинного покрытия и максимального паросочетания===
Вершинным покрытием <tex>VC</tex> <tex>(vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется такое подмножество множества вершин графа <tex>V</tex>, что каждому ребру <tex>G</tex> инцидентна хотя бы одна вершина из <tex>VC</tex>.
+
{{Определение|definition=
}}
+
'''Максимальным''' [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|'''паросочетанием''']] ''(англ. maximum matching)'' в [[Двудольные графы и раскраска в 2 цвета|двудольном графе]] <tex>G</tex> называется паросочетание максимальной мощности.
{{Определение|neat=neat|definition=
 
Минимальным вершинным покрытием <tex>MVC</tex> <tex>(minimum</tex> <tex>vertex</tex> <tex>covering)</tex> графа <tex>G</tex> называется вершинное покрытие минимальной мощности.  
 
 
}}
 
}}
  
<br/><br/>
+
{{Теорема
 
+
|author=Кёниг
<br/>
+
|neat = neat|statement=
<br/>
 
<br/>
 
<br/>
 
 
 
==Связь MM и MVC в двудольном графе==
 
===Теорема о мощности MVC и MM===
 
{{Теорема|statement=
 
 
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
 
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
 
|proof=
 
|proof=
Пусть в <tex>G</tex> построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания &ndash; так, чтобы они шли из левой доли в правую. Запустим [[Обход_в_глубину,_цвета_вершин|обход в глубину]] из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода.
+
Пусть в <tex>G</tex> построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания так, чтобы они шли из левой доли в правую. Запустим [[Обход_в_глубину,_цвета_вершин|обход в глубину]] из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода.
Тогда <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> правая и левая доли соответственно, <tex>L^+, R^+</tex> вершины правой и левой доли, посещенные обходом, <tex>L^-, R^-</tex> не посещенные обходом вершины.
 
Тогда в <tex>G</tex> могут быть следующие ребра:
 
Тогда в <tex>G</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>.  
 
*Из вершин <tex>L^-</tex> в вершины <tex>R^+</tex>.  
 
*Из вершин <tex>L^-</tex> в вершины <tex>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>R^-</tex> в <tex>L^+</tex> быть не может, т.к. если такое ребро <tex>uv</tex> существует, то оно &ndash; ребро паросочетания. Тогда вершина <tex>v</tex> насыщена паросочетанием. Но т.к. <tex>v \in L^+</tex>, то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро <tex>wv, w \in R^+</tex>. Но тогда <tex>v</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>G</tex> является либо <tex>L</tex>, либо <tex>R</tex>, либо <tex>L^- \cup R^+</tex>.
 
В <tex>R^+</tex> не насыщенных паросочетанием вершин быть не может, т.к. иначе в <tex>G</tex> существует дополняющая цепь, что противоречит максимальности построенного паросочетания.
 
В <tex>R^+</tex> не насыщенных паросочетанием вершин быть не может, т.к. иначе в <tex>G</tex> существует дополняющая цепь, что противоречит максимальности построенного паросочетания.
 
В <tex>L^-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L^+</tex>. Тогда т.к. ребер из паросочетания между <tex>R^+</tex>
 
В <tex>L^-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L^+</tex>. Тогда т.к. ребер из паросочетания между <tex>R^+</tex>
и <tex>L^-</tex> нет, то каждому ребру <tex>MM</tex> инцидентна ровно одна вершина из <tex>L^- \cup R^+</tex>.
+
и <tex>L^-</tex> нет, то каждому ребру максимального паросочетания инцидентна ровно одна вершина из <tex>L^- \cup R^+</tex>.  
 
+
Тогда <tex>|L^- \cup R^+|</tex> равна мощности максимального паросочетания. Множество вершин <tex>L^- \cup R^+</tex> является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия.
Тогда <tex>|L^- \cup R^+| = |MM| \le \min(|L|, |R|)</tex>. Значит, минимальным вершинным покрытием является <tex>L^- \cup R^+</tex> и <tex>|MVC| = |MM|</tex>.
 
 
}}
 
}}
  
===Алгоритм построения MVC===
+
===Алгоритм построения минимального вершинного покрытия===
 
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
 
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
*Построить максимальное паросочетание.
+
#Построить максимальное паросочетание.
*Ориентировать ребра:
+
#Ориентировать ребра:
**Из паросочетания &ndash; из правой доли в левую.
+
#*Из паросочетания из правой доли в левую.
**Не из паросочетания &ndash; из левой доли в правую.
+
#*Не из паросочетания из левой доли в правую.
*Запустить обход в глубину из всех свободных вершин левой доли, построить множества <tex>L^+,L^-,R^+,R^-,</tex>.
+
#Запустить обход в глубину из всех свободных вершин левой доли, построить множества <tex>L^+,L^-,R^+,R^-</tex>.
*В качестве результата взять <tex>L^- \cup R^+</tex>.
+
#В качестве результата взять <tex>L^- \cup R^+</tex>.
 +
 
 +
==См. также ==
 +
*[[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]]
 +
*[[Связь_вершинного_покрытия_и_независимого_множества|Связь вершинного покрытия и независимого множества]]
 +
 
 +
==Источники информации==
 +
* [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) Википедия {{---}} Теорема Кёнига]
  
== Источники ==
+
[[Категория: Алгоритмы и структуры данных]]
1. [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) Теорема Кёнига].<br/>
+
[[Категория: Задача о паросочетании]]

Версия 22:09, 22 ноября 2018

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

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


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


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


Теорема о мощности минимального вершинного покрытия и максимального паросочетания

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


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

Тогда [math]|L^- \cup R^+|[/math] равна мощности максимального паросочетания. Множество вершин [math]L^- \cup R^+[/math] является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия.
[math]\triangleleft[/math]

Алгоритм построения минимального вершинного покрытия

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

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

См. также

Источники информации