Изменения

==Определения=====Минимальное вершинное покрытие=Связь максимального паросочетания и минимального вершинного покрытия в двудольном графе=={{Определение|neat=neat|definition='''Вершинным покрытием''''' (англ. '''Vertex vertex covering)''') графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>.

{{Определение|neat=neat|definition='''Минимальным вершинным покрытием''''' (англ. '''Minimum minimum vertex covering)''') графа <tex>G=(V,E)</tex> называется вершинное покрытие, состоящее из наименьшего числа вершин.

==Пример==[[Файл:Cover.jpg|left|thumb|left|300px|Множество вершин красного цвета — минимальное вершинное покрытие.]]<brclear="all"/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/><br/> ==Связь максимального паросочетания и минимального вершинного покрытия в двудольном графе==

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

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

== Источники информации==1. * [http://en.wikipedia.org/wiki/K%C3%B6nig's_theorem_(graph_theory) Теорема Кёнига].<br/>