Граф замен — различия между версиями
Строка 1: | Строка 1: | ||
− | |||
− | |||
'''Граф замен''' — специальный [[Основные определения теории графов|ориентированный двудольный граф]], фигурирующий в [[Теорема Эдмондса-Лоулера|теореме Эдмондса-Лоулера]]. | '''Граф замен''' — специальный [[Основные определения теории графов|ориентированный двудольный граф]], фигурирующий в [[Теорема Эдмондса-Лоулера|теореме Эдмондса-Лоулера]]. | ||
− | Пусть | + | Пусть даны матроиды <tex>M_1 = \langle S, I_1 \rangle</tex>, <tex>M_2 = \langle S, I_2 \rangle</tex>, множество <tex>I \in (I_1 \cap I_2)</tex>. Введем граф замен. |
{{Определение | {{Определение | ||
|definition = | |definition = |
Версия 22:59, 14 апреля 2016
Граф замен — специальный ориентированный двудольный граф, фигурирующий в теореме Эдмондса-Лоулера.
Пусть даны матроиды
, , множество . Введем граф замен.Определение: |
Граф замен для двух матроидов | — граф, левой долей которого являются элементы множества , правой — все остальные элементы и в котором проведены ребра , а также
Пусть — кратчайший путь в из в . Тогда алгоритм с помощью этого пути либо определяет максимальность набора , либо позволяет найти набор большей мощности.
Также существует граф замен для одного матроида.
Определение: |
Пусть дан матроид | и независимый сет . Тогда граф замен (или просто ) — это двудольный граф с долями и с рёбрами между и если
Лемма (о единственном паросочетании в подграфе замен, индуцированном кратчайшим путем): |
Пусть дан двудольный граф замен. В его правой доле можно выделить два подмножества вершин . Пусть — кратчайший путь из в . Рассмотрим сужение графа на множество вершин, лежащих в пути .
Тогда в существует единственное полное паросочетание. |
Доказательство: |
Строго говоря, утверждение теоремы не совсем корректно, так как в правой доле полученного графа вершин на одну больше, чем в левой. Поэтому добавим в фиктивную вершину и отнесем ее к левой доле. Пусть путь , где — фиктивная вершина (рис. 1).Существование полного паросочетания очевидно — это ребра .Предположим, что существует другое паросочетание Противоречие. . Тогда пусть . Обозначим как . Заметим, что и поэтому не может быть , ведь — минимальное из соответствующего множества. Так же невозможно , поскольку тогда и имели бы одинаковую пару. Следовательно, (рис. 2). Это значит, что существует путь короче, чем . |