Изменения

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

Паросочетанием <tex>M</tex> '''Вершинным покрытием''' ''(англ. vertex covering)'' графа <tex>G=(matchingV,E)</tex> в графе называется такое подмножество <tex>GS</tex> называется такое подмножество множества ребер вершин графа <tex>ЕV</tex>,что каждая вершина <tex>G</tex> инцидентна<br/> не более чем одному ребру любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>MS</tex>.

Максимальным паросочетанием <tex>MM</tex> <tex>'''Минимальным вершинным покрытием''' ''(maximum</tex> <tex>matching)</tex> в графе <tex>G</tex> называется паросочетание максимальной мощностиангл.}}{{Определение|definition=Вершинным покрытием <tex>VC</tex> <tex>(minimum vertex</tex> <tex>covering)</tex> '' графа <tex>G=(V,E)</tex> называется такое подмножество множества вершин графа <tex>V</tex>вершинное покрытие, что каждому ребру <tex>G</tex><br/> инцидентна хотя бы одна вершина состоящее из <tex>VC</tex>наименьшего числа вершин.

Минимальным вершинным покрытием <tex>MVС</tex> <tex>'''Максимальным''' [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|'''паросочетанием''']] ''(minimum</tex> <tex>vertex</tex> <tex>coveringангл. maximum matching)</tex> графа '' в [[Двудольные графы и раскраска в 2 цвета|двудольном графе]] <tex>G</tex> называется вершинное покрытие минимальной паросочетание максимальной мощности.

==Связь MM и MVC в двудольном графе=={{Теорема|author=Кёниг|neat = neat|statement=

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

[[Файл:bipartdfs_right.jpg|thumb|center|300px|Доли <tex>L^+, L^-, R^+, R^-</tex> и ребра между ними.]]*Из вершин <tex>L_L^+</tex> в вершины <tex>R_R^+</tex> и из вершин <tex>R_R^+</tex> в вершины <tex>L_L^+</tex>.*Из вершин <tex>L_L^-</tex> в вершины <tex>R_R^-</tex> и из вершин <tex>R_R^-</tex> в вершины <tex>L_L^-</tex>. *Из вершин <tex>L_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>L^- \cup R^+</tex>. Тогда <tex>|L^- \cup R^+|</tex> равна мощности максимального паросочетания. Множество вершин <tex>L^- \cup R^+</tex> является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия.}} ===Алгоритм построения минимального вершинного покрытия===Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:#Построить максимальное паросочетание.#Ориентировать ребра:#*Из паросочетания — из правой доли в левую.#*Не из паросочетания — из левой доли в правую.#Запустить обход в глубину из всех свободных вершин левой доли, построить множества <tex>R_L^+,L^-,R^+,R^-</tex>.#В качестве результата взять <tex>L^- \cup 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_+<* [http:/tex> не насыщенных паросочетанием вершин быть не может, т.к. иначе в <tex>G</tex> существует дополняющая цепь, что противоречит максимальности построенного паросочетанияen.В <tex>L_-</tex> свободных вершин быть не может, тwikipedia.к. все они должны находиться в <tex>L_+<org/tex>. Тогда т.к. ребер из паросочетания между <tex>R_+<wiki/tex>и <tex>L_K%C3%B6nig's_theorem_(graph_theory) Википедия {{--</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|Пример максимального паросочетанияЗадача о паросочетании]]