76
правок
Изменения
м
Пусть Очевидно, что либо первое, либо последнее ребро в цепи — имеет вид <tex>(ab)\in M</tex>, где <tex>a \in A, b \in B, \deg b = 1</tex>, тогда положим . Положим <tex>a_n=a, b_n=b</tex>. ТДля <tex>G \setminus \{a_n \cup b_n \}</tex> утверждение верно по предположению индукции. С другой стороны, т. к. <tex>\deg b_n=\deg b = 1</tex>, то <tex>(a_i b_n) \notin G</tex> при <tex>i<n</tex>, т. е. поэтому для <tex>j = n</tex> утверждение верно. Удалим из <tex>G</tex> вершины <tex>a_n</tex> и <tex>b_n</tex>. По предположению индукции для полученного графа утверждение также верно.
Нет описания правки
{{Утверждение
|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>(y_i z_ia_i b_i)</tex>.
|proof=Индукция по <tex>|A|</tex>.<br/>
При <tex>|A|=1</tex> утверждение очевидно. <br/>
Пусть <tex>|A|=n>1</tex>. Будем строить [[Теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|чередующуюся цепь]], добавляя по очереди ребро, входящее в <tex>M</tex>, и ребро, не входящее в <tex>M</tex>. Заметим, что в процессе добавления рёбер невозможно попадение в уже посещённую вершину — в противном случае мы получим цикл чётной длины, что противоречит единственности паросочетания. Если последнее добавленное ребро не принадлежит <tex>M</tex>, то присоединим к цепи ребро из <tex>M</tex>, инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из <tex>M</tex> при достижении вершины [[Основные определения теории графов#Степень вершины|степени]] 1. <br/>
}}
