Граф замен

Граф замен [math]D_{M_1, M_2}(I)[/math]

Граф замен — специальный ориентированный двудольный граф, фигурирующий в теореме Эдмондса-Лоулера.

Пусть [math]I[/math] — текущее независимое множество, построенное алгоритмом для матроидов [math]M_1 = \langle S, I_1 \rangle[/math], [math]M_2 = \langle S, I_2 \rangle[/math]. Введем граф замен [math]D_{M_1, M_2}(I)[/math], левой долей которого являются элементы множества [math]I[/math], правой — все остальные элементы [math]S[/math]. Проведем все имеющиеся ребра

[math](y, z): y \in I, z \in S \setminus I, I \setminus y \cup z \in I_1[/math],

а также

[math](z', y'): y' \in I, z' \in S \setminus I, I \setminus y' \cup z' \in I_2[/math].

Пусть [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 \}, P[/math] — кратчайший путь в [math]D_{M_1, M_2}(I)[/math] из [math]X_1[/math] в [math]X_2[/math]. Тогда алгоритм с помощью этого пути либо определяет максимальность набора [math]I[/math], либо позволяет найти набор большей мощности.

Также существует граф замен для одного матроида. Он определяется так: пусть дан матроид [math]M = (S, I)[/math] и независимый сет [math]I \in I[/math]. Тогда граф замен [math]D_{M}(I)[/math] (или просто [math]D(I)[/math]) это двудольный граф с долями [math]I[/math] и [math]S \setminus I[/math] с рёбрами между [math]y \in I[/math] и [math]x \in S \setminus I[/math] если [math] I - y + x \in I [/math]

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

Пусть дан двудольный граф замен. В его правой доле можно выделить два подмножества вершин [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]

Источники информации

• Chandra Chekuri — Combinatorial Optimization
• Michel X. Goemans — Matroid Intersection