76
правок
Изменения
м
Нет описания правки
|proof=Индукция по <tex>|A|</tex>.<br/>
При <tex>|A|=1</tex> утверждение очевидно. <br/>
Пусть <tex>|A|=n>1</tex>(для <tex>|A|=n-1</tex> утверждение верно). Возьмем произвольную вершину в левой доли. Будем строить из неё [[Теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|чередующуюся цепь]], добавляя по очереди ребро, входящее в <tex>M</tex>, и ребро, не входящее в <tex>M</tex>. Заметим, что в процессе добавления рёбер невозможно попадение в уже посещённую вершину — в противном случае мы получим цикл такой путь не содержит циклов (циклы нечётной длины невозможны, т. к. граф двудольный, циклы чётной длины, что противоречит отсутствуют из-за единственности паросочетания). Если последнее добавленное ребро не принадлежит <tex>M</tex>, то присоединим к цепи ребро из <tex>M</tex>, инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из <tex>M</tex> при достижении вершины [[Основные определения теории графов#Степень вершины|степени]] 1. <br/>ОчевидноТаким образом, что либо первое, либо последнее ребро в цепи имеет вид <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 = 1</tex>, то <tex>(a_i b_n) \notin G</tex> при <tex>i<n</tex>, поэтому для <tex>j = n</tex> утверждение также верно.<br/>
}}
{{Лемма
|about=
о единственном паросочетании в графе замен
|statement= Дан [[Определение матроида|матроид]] <tex>M = \langle X,I \rangle </tex>. Пусть двудольный граф <tex>G_M(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> содержит единственное полное паросочетание на <tex>A \oplus B</tex>, где <tex>A\in I</tex> и <tex>|A| = |B|</tex>. Тогда <tex>B \in I</tex>.
|proof=
