Изменения
Нет описания правки
===Минимальное вершинное покрытие===
{{Определение|neat=neat|definition=
'''Вершинным покрытием''' (англ. '''Vertex covering''', '''VC''') графа <tex>G=(V,E)</tex> называется такое подмножество <tex>S</tex> множества вершин графа <tex>V</tex>, что любое ребро этого графа инцидентно хотя бы одной вершине из множества <tex>S</tex>.
'''Минимальным вершинным покрытием''' (англ. '''Minimum vertex covering''', '''MVC''') графа <tex>G=(V,E)</tex> называется вершинное покрытие, состоящее из наименьшего числа вершин.
}}
<br/>
<br/>
<br/>
<br/>
<br/>
==Пример==[[Файл:Cover.jpg|300px]]<br/>Множество вершин красного цвета - минимальное вершинное покрытие.<br/>
<br/>
Тогда <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> могут быть следующие ребра:
[[Файл:bipartdfs_right.jpg|thumb|rightcenter|240x240px300px|Доли <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>.
