Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем
Версия от 07:24, 27 июня 2011; 192.168.0.2 (обсуждение)
Лемма: |
Пусть дан двудольный граф — граф замен. В его правой доле можно выделить два подмножества вершин . Пусть - кратчайший путь из в . Рассмотрим сужение графа на множество вершин, лежащих в пути .
Тогда в существует единственное полное паросочетание. |