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

Определения

Определение:

Паросочетанием [math]M[/math] [math](matching)[/math] в графе [math]G[/math] называется такое подмножество множества ребер графа [math]Е[/math], что каждая вершина [math]G[/math] инцидентна не более чем одному ребру из [math]M[/math].

Определение:

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

Определение:

Вершинным покрытием [math]VC[/math] [math](vertex[/math] [math]covering)[/math] графа [math]G[/math] называется такое подмножество множества вершин графа [math]V[/math], что каждому ребру [math]G[/math] инцидентна хотя бы одна вершина из [math]VC[/math].

Определение:

Минимальным вершинным покрытием [math]MVС[/math] [math](minimum[/math] [math]vertex[/math] [math]covering)[/math] графа [math]G[/math] называется вершинное покрытие минимальной мощности.

Связь MM и MVC в двудольном графе

Теорема:

В произвольном двудольном графе мощность максимального паросочетания равна мощности минимального вершинного покрытия.

Пример максимального паросочетания