Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем — различия между версиями
Martoon (обсуждение | вклад) м |
|||
| Строка 1: | Строка 1: | ||
{{Лемма | {{Лемма | ||
|statement = | |statement = | ||
| − | Пусть дан двудольный граф <tex> | + | Пусть дан двудольный граф <tex>\{(y, z) \mid y \in I, z \in S \setminus I, I \setminus y \cup z \in I_1, (z', y') \mid y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in I_2\}</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]] |
| − | + | Строго говоря, утверждение теоремы не совсем корректно, так как в правой доле полученного графа <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). | |
| − | + | ||
| − | + | Существование полного паросочетания очевидно - это ребра <tex>(a_i,b_i)</tex>. | |
| − | + | ||
| + | Предположим, что существует другое паросочетание <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>. | ||
| + | Противоречие. | ||
}} | }} | ||
| − | [[Категория:Алгоритмы и структуры данных]] | + | [[Категория: Алгоритмы и структуры данных]] |
| − | [[Категория:Матроиды]] | + | [[Категория: Матроиды]] |
| + | [[Категория: Пересечение матроидов]] | ||
Версия 00:30, 13 июня 2015
| Лемма: |
Пусть дан двудольный граф — граф замен. В его правой доле можно выделить два подмножества вершин . Пусть - кратчайший путь из в . Рассмотрим сужение графа на множество вершин, лежащих в пути .
Тогда в существует единственное полное паросочетание. |
| Доказательство: |
|
Строго говоря, утверждение теоремы не совсем корректно, так как в правой доле полученного графа вершин на одну больше, чем в левой. Поэтому добавим в фиктивную вершину и отнесем ее к левой доле. Пусть путь , где - фиктивная вершина (рис. 1). Существование полного паросочетания очевидно - это ребра . Предположим, что существует другое паросочетание . Тогда пусть . Обозначим как . Заметим, что и поэтому не может быть , ведь - минимальное из соответствующего множества. Так же невозможно , поскольку тогда и имели бы одинаковую пару. Следовательно, (рис. 2). Это значит, что существует путь короче, чем . Противоречие. |
