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

Определения

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

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

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

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

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

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

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

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