Викиконспекты - Вклад участника [ru]

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

2011-06-27T06:24:45Z

Святушенко:

{{Лемма
|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>G'</tex> существует единственное полное паросочетание.
|proof =
[[Файл:Граф_индуцированный_кратчайшим_путем.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]]
 Существование паросочетания очевидно - это ребра <tex>(a_i,b_i)</tex>.
 Предположим, что существует другое паросочетание <tex>(a_i, b_{ji})</tex>. Тогда пусть <tex>i_0 = min \{ i \: | \: j_i . Обозначим <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>.
 Противоречие.
}}

Файл:Фрагмент паросочетания.png

2011-06-27T06:24:20Z

Святушенко:

Файл:Граф индуцированный кратчайшим путем.png

2011-06-27T06:16:07Z

Святушенко: загружена новая версия «Файл:Граф индуцированный кратчайшим путем.png»

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

2011-06-27T06:08:07Z

Святушенко:

{{Лемма
|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>G'</tex> существует единственное полное паросочетание.
|proof =
[[Файл:Граф_индуцированный_кратчайшим_путем.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]]
 Существование паросочетания очевидно - это ребра <tex>(a_i,b_i)</tex>.
 Предположим, что существует другое паросочетание <tex>(a_i, b_{ji})</tex>. Тогда пусть <tex>i_0 = min \{ i \: | \: j_i . Обозначим <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}}, \ldots, a_k, b_k )</tex> короче, чем <tex>P</tex>.
 Противоречие.
}}

Файл:Паросочетанька.png

2011-06-27T06:04:54Z

Святушенко:

Файл:Граф индуцированный кратчайшим путем.png

2011-06-27T05:59:12Z

Святушенко: