Изменения

Перейти к: навигация, поиск
Нет описания правки
{{Утверждение
|statement=Пусть двудольный граф <tex>G</tex> содержит единственное полное паросочетание <tex>M</tex>. Тогда можо можно упорядочить вершины левой <tex>(a_i \in A)</tex> и правой <tex>(b_i \in B)</tex> долей таким образом, что <tex>\forall j > i : (a_i b_j) \notin G</tex>. При этом рёбра паросочетания будут иметь вид <tex>(a_i b_i)</tex>.
|proof=Индукция по <tex>|A|</tex>.<br/>
Анонимный участник

Навигация