Лемма о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем — различия между версиями
(Перенаправление на Граф замен) |
|||
Строка 1: | Строка 1: | ||
+ | #перенаправление [[Граф замен]] | ||
{{Лемма | {{Лемма | ||
|statement = | |statement = |
Текущая версия на 09:41, 10 апреля 2016
Перенаправление на:
Лемма: |
Пусть дан двудольный граф замен. В его правой доле можно выделить два подмножества вершин . Пусть — кратчайший путь из в . Рассмотрим сужение графа на множество вершин, лежащих в пути .
Тогда в существует единственное полное паросочетание. |
Доказательство: |
Строго говоря, утверждение теоремы не совсем корректно, так как в правой доле полученного графа вершин на одну больше, чем в левой. Поэтому добавим в фиктивную вершину и отнесем ее к левой доле. Пусть путь , где — фиктивная вершина (рис. 1).Существование полного паросочетания очевидно — это ребра .Предположим, что существует другое паросочетание Противоречие. . Тогда пусть . Обозначим как . Заметим, что и поэтому не может быть , ведь — минимальное из соответствующего множества. Так же невозможно , поскольку тогда и имели бы одинаковую пару. Следовательно, (рис. 2). Это значит, что существует путь короче, чем . |