Лемма о единственном паросочетании в графе замен — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{{Утверждение
 +
|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_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/>
 +
Пусть последнее ребро в цепи — <tex>(ab)</tex>, где <tex>a \in A, b \in B</tex>, тогда положим <tex>a_n=a, b_n=b</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>. По предположению индукции для полученного графа утверждение также верно.
 +
}}
 +
 +
 
{{Лемма
 
{{Лемма
 
|about=
 
|about=
Строка 5: Строка 15:
 
|proof=  
 
|proof=  
 
[[Файл:Graph replacement.png|thumb|left|160px|]]
 
[[Файл:Graph replacement.png|thumb|left|160px|]]
Заметим, что т. к. в графе <tex>G_M(A)</tex> нет другого паросочетания, то в нем нет циклов четной длины, значит, граф является ациклическим. Упорядочим вершины левой <tex>(y_i \in A \setminus B)</tex> и правой <tex>(z_j \in B \setminus A)</tex> долей таким образом, что <tex>\forall j < i : (y_i z_j) \notin G_M(A)</tex>. Заметим также, что при таком упорядочивании ребра паросочетания имеют вид <tex>(y_i z_i)</tex>. Действительно, ребро в первую вершину правой доли может идти только из первой вершины левой доли. Аналогично во вторую вершину правой доли ведет ребро из второй вершины левой доли и, возможно, ребро из первой вершины, которое уже не может быть использовано в паросочетании и т. д.
+
Упорядочим вершины левой <tex>(y_i \in A \setminus B)</tex> и правой <tex>(z_j \in B \setminus A)</tex> долей таким образом, что <tex>\forall j > i : (y_i z_j) \notin G_M(A)</tex>. При таком упорядочивании ребра паросочетания имеют вид <tex>(y_i z_i)</tex>.
  
Требуется доказать, что <tex>B</tex> независимо. Предположим обратное. Пусть <tex>B \notin I</tex>, тогда существует [[Теорема о циклах|цикл]] <tex>C \subset B</tex>.<br/> Выберем минимальное <tex>i</tex> такое, что <tex>C \subset (A \cap B) \cup \{z_1..z_i\}</tex>. Т. к. <tex>\forall j < i : (y_i z_j) \notin G_M(A)</tex>, то <tex>A \setminus y_i \cup z_j \notin I</tex>, следовательно, <tex>C \setminus z_i \subset \langle A \setminus y_i \rangle </tex>. По [[Оператор замыкания для матроидов#theorem|свойствам замыкания 1 и 3]] получаем:<br/>
+
Требуется доказать, что <tex>B</tex> независимо. Предположим обратное. Пусть <tex>B \notin I</tex>, тогда существует [[Теорема о циклах|цикл]] <tex>C \subset B</tex>.<br/> Выберем минимальное <tex>i</tex> такое, что <tex>z_i \in C</tex>. Т. к. <tex>\forall j > i : (y_i z_j) \notin G_M(A)</tex>, то <tex>A \setminus y_i \cup z_j \notin I</tex>, следовательно, <tex>C \setminus z_i \subset \langle A \setminus y_i \rangle </tex>. По [[Оператор замыкания для матроидов#theorem|свойствам замыкания 1 и 3]] получаем:<br/>
 
<tex>C \setminus z_i \subset \langle A \setminus y_i \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle \langle A \setminus y_i \rangle \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex> <br/>
 
<tex>C \setminus z_i \subset \langle A \setminus y_i \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle \langle A \setminus y_i \rangle \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex> <br/>
Т. к. <tex>z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex>, то <tex>A \setminus y_i \cup z_i \notin I</tex>, т. е. в <tex>G_M(A)</tex> не существует ребра <tex>(y_i z_i)</tex>. Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.  
+
Т. к. <tex>z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle</tex>, то <tex>A \setminus y_i \cup z_i \notin I</tex>, т. е. в <tex>G_M(A)</tex> не существует ребра <tex>(y_i z_i)</tex>. Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.
 
}}
 
}}
 +
 +
== Источник ==
 +
''Chandra Chekuri'' — [http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture16.pdf '''Combinatorial Optimization'''], с. 6

Версия 04:22, 18 июня 2011

Утверждение:
Пусть двудольный граф [math]G[/math] содержит единственное полное паросочетание [math]M[/math]. Тогда можо упорядочить вершины левой [math](a_i \in A)[/math] и правой [math](b_i \in B)[/math] долей таким образом, что [math]\forall j \gt i : (a_i b_j) \notin G[/math]. При этом рёбра паросочетания будут иметь вид [math](y_i z_i)[/math].
[math]\triangleright[/math]

Индукция по [math]|A|[/math].
При [math]|A|=1[/math] утверждение очевидно.
Пусть [math]|A|=n\gt 1[/math]. Будем строить чередующуюся цепь, добавляя по очереди ребро, входящее в [math]M[/math], и ребро, не входящее в [math]M[/math]. Заметим, что в процессе добавления рёбер невозможно попадение в уже посещённую вершину — в противном случае мы получим цикл чётной длины, что противоречит единственности паросочетания. Если последнее добавленное ребро не принадлежит [math]M[/math], то присоединим к цепи ребро из [math]M[/math], инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из [math]M[/math] при достижении вершины степени 1.

Пусть последнее ребро в цепи — [math](ab)[/math], где [math]a \in A, b \in B[/math], тогда положим [math]a_n=a, b_n=b[/math]. Т. к. [math]\deg b_n=\deg b = 1[/math], то [math](a_i b_n) \notin G[/math] при [math]i\lt n[/math], т. е. для [math]j = n[/math] утверждение верно. Удалим из [math]G[/math] вершины [math]a_n[/math] и [math]b_n[/math]. По предположению индукции для полученного графа утверждение также верно.
[math]\triangleleft[/math]


Лемма (о единственном паросочетании графе замен):
Дан матроид [math]M = \langle X,I \rangle [/math]. Пусть двудольный граф [math]G_M(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}[/math] содержит единственное полное паросочетание на [math]A \oplus B[/math], где [math]A\in I[/math] и [math]|A| = |B|[/math]. Тогда [math]B \in I[/math].
Доказательство:
[math]\triangleright[/math]
Graph replacement.png

Упорядочим вершины левой [math](y_i \in A \setminus B)[/math] и правой [math](z_j \in B \setminus A)[/math] долей таким образом, что [math]\forall j \gt i : (y_i z_j) \notin G_M(A)[/math]. При таком упорядочивании ребра паросочетания имеют вид [math](y_i z_i)[/math].

Требуется доказать, что [math]B[/math] независимо. Предположим обратное. Пусть [math]B \notin I[/math], тогда существует цикл [math]C \subset B[/math].
Выберем минимальное [math]i[/math] такое, что [math]z_i \in C[/math]. Т. к. [math]\forall j \gt i : (y_i z_j) \notin G_M(A)[/math], то [math]A \setminus y_i \cup z_j \notin I[/math], следовательно, [math]C \setminus z_i \subset \langle A \setminus y_i \rangle [/math]. По свойствам замыкания 1 и 3 получаем:
[math]C \setminus z_i \subset \langle A \setminus y_i \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle \langle A \setminus y_i \rangle \rangle \Rightarrow \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle[/math]

Т. к. [math]z_i \in \langle C \setminus z_i \rangle \subset \langle A \setminus y_i \rangle[/math], то [math]A \setminus y_i \cup z_i \notin I[/math], т. е. в [math]G_M(A)[/math] не существует ребра [math](y_i z_i)[/math]. Но тогда, как было отмечено ранее, не существует полного паросочетания. Получили противоречие.
[math]\triangleleft[/math]

Источник

Chandra ChekuriCombinatorial Optimization, с. 6