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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
 
(не показано 14 промежуточных версий 5 участников)
Строка 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>(a_i b_i)</tex>.
+
|statement=Пусть [[Двудольные_графы_и_раскраска_в_2_цвета|двудольный граф]] <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/>
 
|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>|A|=1</tex> утверждение очевидно. <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> утверждение также верно.
+
* Переход
 +
*: Пусть <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> при достижении вершины [[Основные определения теории графов#Степень вершины|степени]] <tex>1</tex>. <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/>
 
}}
 
}}
  
Строка 11: Строка 14:
 
{{Лемма
 
{{Лемма
 
|about=
 
|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>.
+
|statement= Дан [[Определение матроида|матроид]] <tex>M = \langle X,I \rangle </tex>. Пусть двудольный граф <tex>G_M(A) = \{ (x, y) \mid 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=  
 
|proof=  
 
[[Файл:Graph replacement.png|thumb|left|160px|]]
 
[[Файл:Graph replacement.png|thumb|left|160px|]]
 
Упорядочим вершины левой <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>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>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
+
* [http://www.cs.illinois.edu/class/sp10/cs598csc/Lectures/Lecture16.pdf '''Chandra Chekuri — Combinatorial Optimization], с. 6
 +
 
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Матроиды]]
 +
[[Категория:Пересечение матроидов]]

Текущая версия на 10:04, 27 апреля 2016

Утверждение:
Пусть двудольный граф [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](a_i b_i)[/math].
[math]\triangleright[/math]

Индукция по [math]|A|[/math].

  • База
    При [math]|A|=1[/math] утверждение очевидно.
  • Переход
    Пусть [math]|A|=n\gt 1[/math] (для [math]|A|=n-1[/math] утверждение верно). Возьмем произвольную вершину в левой доли. Будем строить из неё чередующуюся цепь, добавляя по очереди ребро, входящее в [math]M[/math], и ребро, не входящее в [math]M[/math]. Заметим, что такой путь не содержит циклов (циклы нечётной длины невозможны, так как граф двудольный, циклы чётной длины отсутствуют из-за единственности паросочетания). Если последнее добавленное ребро не принадлежит [math]M[/math], то присоединим к цепи ребро из [math]M[/math], инцидентное последней вершине. Значит, построение цепи прервется только при добавлении ребра из [math]M[/math] при достижении вершины степени [math]1[/math].
Таким образом, последнее ребро в цепи имеет вид [math](ab) \in M[/math], где [math]a \in A, b \in B, \deg b = 1[/math]. Положим [math]a_n=a, b_n=b[/math]. Для [math]G \setminus \{a_n \cup b_n \}[/math] утверждение верно по предположению индукции. С другой стороны, так как [math]\deg b_n = 1[/math], то [math](a_i b_n) \notin G[/math] при [math]i\lt n[/math], поэтому для [math]j = n[/math] утверждение также верно.
[math]\triangleleft[/math]


Лемма (о единственном паросочетании в графе замен):
Дан матроид [math]M = \langle X,I \rangle [/math]. Пусть двудольный граф [math]G_M(A) = \{ (x, y) \mid 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]

Источники информации