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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Перенаправление на Граф замен)
 
(не показано 5 промежуточных версий 4 участников)
Строка 1: Строка 1:
 +
#перенаправление [[Граф замен]]
 
{{Лемма
 
{{Лемма
 
|statement =
 
|statement =
−
Пусть дан двудольный граф <tex>G(A) = \{ (x, y) | x \in A, y \notin A, A \setminus x \cup y \in I \}</tex> — граф замен. В его правой доле можно выделить два подмножества вершин <tex>X_1 = \{z \in S \setminus I | I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I | I \cup z \in I_2 \}</tex>. Пусть <tex>P</tex> - кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. Рассмотрим сужение <tex>G'</tex> графа <tex>G</tex> на множество вершин, лежащих в пути <tex>P</tex>.
+
Пусть дан двудольный [[Граф замен для двух матроидов|граф замен]]. В его правой доле можно выделить два подмножества вершин <tex>X_1 = \{z \in S \setminus I \mid I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in I_2 \}</tex>. Пусть <tex>P</tex> — кратчайший путь из <tex>X_1</tex> в <tex>X_2</tex>. Рассмотрим сужение <tex>G'</tex> графа <tex>G</tex> на множество вершин, лежащих в пути <tex>P</tex>.
−
<br>Тогда в <tex>G'</tex> существует единственное полное паросочетание.
+
<br>Тогда в <tex>G'</tex> существует единственное [[Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях#Паросочетание в двудольном графе|полное паросочетание]].
 
|proof =
 
|proof =
−
[[Файл:Граф_индуцированный_кратчайшим_путем.png | thumb | left | рис. 1]]
+
[[Файл:Граф_индуцированный_кратчайшим_путем.png | thumb | left | Рис. 1]]
−
Строго говоря утверждение теоремы не совсем корректно, так как в правой доле полученного графа <tex>G'</tex> вершин на одну больше, чем в левой. Поэтому добавим в <tex>G'</tex> фиктивную вершину и отнесем ее к левой доле. Пусть путь <tex>P = (a_1, b_1, a_2, b_2, \ldots , a_k, b_k)</tex>, где  <tex>a_1</tex> - фиктивная вершина (рис.1).  
+
[[Файл:Фрагмент_паросочетания.png‎ | thumb | right | Рис. 2]]
−
[[Файл:Фрагмент_паросочетания.png‎  | thumb | right | рис. 2]]
+
Строго говоря, утверждение теоремы не совсем корректно, так как в правой доле полученного графа <tex>G'</tex> вершин на одну больше, чем в левой. Поэтому добавим в <tex>G'</tex> фиктивную вершину и отнесем ее к левой доле. Пусть путь <tex>P = (a_1, b_1, a_2, b_2, \ldots , a_k, b_k)</tex>, где  <tex>a_1</tex> — фиктивная вершина (рис. 1).  
−
<br>Существование паросочетания очевидно - это ребра  <tex>(a_i,b_i)</tex>.
+
 
−
<br>Предположим, что существует другое паросочетание <tex>(a_i, b_{ji})</tex>. Тогда пусть <tex>i_0 = min \{ i \: | \: j_i < i \}</tex>. Обозначим <tex>j_{i_0}</tex> как <tex>i_1</tex>. Заметим, что <tex>i_1 < i_0</tex> и поэтому не может быть <tex>j_{i_1} < i_1</tex>, ведь <tex>i_0</tex> - минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = i_1</tex>, поскольку тогда <tex>a_{i_0}</tex> и <tex>a_{i_1}</tex> имели бы одинаковую пару. Следовательно, <tex>j_{i_1} > i_1</tex> (рис.2). Это значит, что существует путь <tex>P_1 = (a_1, b_1, \ldots, a_{i_1}, b_{j_{i_1}}, a_{j_{i_1} + 1}, \ldots, a_k, b_k )</tex> короче, чем <tex>P</tex>.  
+
Существование полного паросочетания очевидно — это ребра  <tex>(a_i,b_i)</tex>.
−
<br> Противоречие.
+
 
 +
Предположим, что существует другое паросочетание <tex>(a_i, b_{j_i})</tex>. Тогда пусть <tex>i_0 = \min \{ i \: \mid \: j_i < i \}</tex>. Обозначим <tex>j_{i_0}</tex> как <tex>i_1</tex>. Заметим, что <tex>i_1 < i_0</tex> и поэтому не может быть <tex>j_{i_1} < i_1</tex>, ведь <tex>i_0</tex> — минимальное из соответствующего множества. Так же невозможно <tex>j_{i_1} = i_1</tex>, поскольку тогда <tex>a_{i_0}</tex> и <tex>a_{i_1}</tex> имели бы одинаковую пару. Следовательно, <tex>j_{i_1} > i_1</tex> (рис. 2). Это значит, что существует путь <tex>P_1 = (a_1, b_1, \ldots, a_{i_1}, b_{j_{i_1}}, a_{j_{i_1} + 1}, \ldots, a_k, b_k )</tex> короче, чем <tex>P</tex>.  
 +
Противоречие.
 
}}
 
}}
 +
 +
[[Категория: Алгоритмы и структуры данных]]
 +
[[Категория: Матроиды]]
 +
[[Категория: Пересечение матроидов]]

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

Перенаправление на:

Лемма:
Пусть дан двудольный граф замен. В его правой доле можно выделить два подмножества вершин [math]X_1 = \{z \in S \setminus I \mid I \cup z \in I_1 \}, X_2 = \{z \in S \setminus I \mid I \cup z \in I_2 \}[/math]. Пусть [math]P[/math] — кратчайший путь из [math]X_1[/math] в [math]X_2[/math]. Рассмотрим сужение [math]G'[/math] графа [math]G[/math] на множество вершин, лежащих в пути [math]P[/math].
Тогда в [math]G'[/math] существует единственное полное паросочетание.
Доказательство:
[math]\triangleright[/math]
Рис. 1
Рис. 2

Строго говоря, утверждение теоремы не совсем корректно, так как в правой доле полученного графа [math]G'[/math] вершин на одну больше, чем в левой. Поэтому добавим в [math]G'[/math] фиктивную вершину и отнесем ее к левой доле. Пусть путь [math]P = (a_1, b_1, a_2, b_2, \ldots , a_k, b_k)[/math], где [math]a_1[/math] — фиктивная вершина (рис. 1).

Существование полного паросочетания очевидно — это ребра [math](a_i,b_i)[/math].

Предположим, что существует другое паросочетание [math](a_i, b_{j_i})[/math]. Тогда пусть [math]i_0 = \min \{ i \: \mid \: j_i \lt i \}[/math]. Обозначим [math]j_{i_0}[/math] как [math]i_1[/math]. Заметим, что [math]i_1 \lt i_0[/math] и поэтому не может быть [math]j_{i_1} \lt i_1[/math], ведь [math]i_0[/math] — минимальное из соответствующего множества. Так же невозможно [math]j_{i_1} = i_1[/math], поскольку тогда [math]a_{i_0}[/math] и [math]a_{i_1}[/math] имели бы одинаковую пару. Следовательно, [math]j_{i_1} \gt i_1[/math] (рис. 2). Это значит, что существует путь [math]P_1 = (a_1, b_1, \ldots, a_{i_1}, b_{j_{i_1}}, a_{j_{i_1} + 1}, \ldots, a_k, b_k )[/math] короче, чем [math]P[/math].

Противоречие.
[math]\triangleleft[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Лемма_о_единственном_паросочетании_в_подграфе_замен,_индуцированном_кратчайшим_путем&oldid=53169»