Изменения
Нет описания правки
===Минимальное вершинное покрытие===
{{Определение|neat=neat|definition=
'''Вершинным покрытием''' (англ. '''Vertex covering''', '''VC''') графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>.
}}
{{Определение|neat=neat|definition=
'''Минимальным вершинным покрытием''' (англ. '''Minimum vertex covering''', '''MVC''') графа <tex>G=(V,E)</tex> называется вершинное покрытие, состоящее из наименьшего числа вершин.
}}
<br/>
==Пример==
[[Файл:Cover.jpg|thumb|left|300px]]<br/>|Множество вершин красного цвета — минимальное вершинное покрытие.<br/>]]
<br/>
<br/><br/><br/><br/><br/>
<br/><br/><br/><br/><br/>
<br/><br/><br/><br/><br/>
<br/><br/><br/><br/><br/>
==Связь максимального паросочетания и минимального вершинного покрытия в двудольном графе==
===Максимальное паросочетаниеТеорема о мощности минимального вершинного покрытия и максимального паросочетания===
{{Определение|definition=
'''Максимальным''' [[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|'''паросочетанием''']] (англ. '''Maximum matching''', '''MM''') в [[Двудольные графы и раскраска в 2 цвета|двудольном графе]] <tex>G</tex> называется паросочетание максимальной мощности.
}}
{{Теорема|neat = neat|statement=
В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.
В <tex>L^-</tex> свободных вершин быть не может, т.к. все они должны находиться в <tex>L^+</tex>. Тогда т.к. ребер из паросочетания между <tex>R^+</tex>
и <tex>L^-</tex> нет, то каждому ребру максимальным паросочетания инцидентна ровно одна вершина из <tex>L^- \cup R^+</tex>.
Тогда <tex>|L^- \cup R^+| = |MM|</tex>равна мощности максимального паросочетания. Множество вершин <tex>L^- \cup R^+</tex> является минимальным вершинным покрытием. Значит мощность максимального паросочетания равна мощности минимального вершинного покрытия.
}}
==См. также ==
[[Теорема_о_максимальном_паросочетании_и_дополняющих_цепях|Теорема о максимальном паросочетании и дополняющих цепях]].
<br>
[[Связь_вершинного_покрытия_и_независимого_множества|Связь вершинного покрытия и независимого множества]].
