Декомпозиция Эдмондса-Галлаи

В этом направлении много усилий приложили Вильям Томас Татт (William Thomas Tutte), Клод Берж (Claude Berge), Джек Эдмондс (Jack Edmonds) и Тибор Галлаи (Tibor Gallai).

Определение:

Дефицитом (англ. deficit) графа $G$ мы будем называть величину: $\mathrm{def}(G) = |V| - 2\alpha (G)$, где $\alpha (G)$ — размер максимального паросочетания в $G$, а $V(G)$ — множество вершин графа $G.$

Определение:

$\mathrm{odd}({G})$ — число нечетных компонент связности в графе ${G}$, где нечетная компонента (англ. odd component) — это компонента связности, содержащая нечетное число вершин.

Лемма:

$(n + |S| + odd(G \setminus S)) \; \equiv \; 0 \; ( mod \; 2) \;$, где $G$ — граф с $n$ вершинами, $S \subset {V}_{G}$

Доказательство:

$\triangleright$

Удалим из графа $G$ множество $S$, получим $t$ компонент связности, содержащих $k_1, k_2 ... k_t$ вершин соответственно. $|S|\; + \; \sum_{i=1}^{k}k_i \; = \; n \;$, так как в сумме это все вершины исходного графа $G$. Возьмем данное равенство по модулю два: $(|S|\; + \; \sum_{i=1}^{k}k_i) \; \equiv \; n \; (mod \; 2)$ В сумме $\sum_{i=1}^{k}(k_i \; mod \; 2)$ число единиц равно числу нечетных компонент $odd(G \setminus S)$. Таким образом, $\forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n \; (mod \; 2) \;$.

$\triangleleft$

Теорема (Бержа):

Для любого графа $G$ выполняется: $\mathrm{def}(G) = \max\limits_{S \subset V(G)} \{\mathrm{odd}(G - S) - |S|\}.$

Доказательство:

$\triangleright$

$\forall S \in V : \; (odd(G \setminus S) + |S|) \; \equiv \; n ( mod \; 2) \;$ Рассмотрим несколько случаев: 1. Если $\max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \; = 0 \;$, тогда для любых $S \in V: \; odd(G \setminus S) \leq |S| \;$, следовательно выполнено условие теоремы Татта, значит, в графе есть совершенное паросочетание, то есть его дефицит равен нулю. 2. Если $\max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \;$, тогда рассмотрим исходный граф $G$ и полный граф $K_k$ с $k$ вершинами, $W$ - вершины $K_k$. Каждую вершину $K_k$ соединим с каждой вершиной $G$. Получим граф $H \; = \; K_k + G \;$, докажем, что для него выполнено условие теоремы Татта. Докажем, что для любых $S \in V_{H}: odd(H \setminus S) \; \leq \; |S| \;$. Рассмотрим $S \; \subset \; V_H\;$: Если $W \not\subset S$, тогда поскольку граф $K_k$ полный и все его вершины связаны с каждой вершиной графа $G$, то граф $H$ связный и $odd(H \setminus S) \; = \; 0 \;$ или $odd(G \setminus S) \; = \; 1 \;$. В случае $odd(H \setminus S) \; = \; 0 \;$ условие очевидно выполняется, так как для любых $S \in G : 0 \; \leq \; |S| \;$. Рассмотрим случай $odd(H \setminus S) \; = \; 1 \;$, $|V_H| \; = \; n \; + \; k \; = \; n \; + \; odd(G \setminus A) \; - \; |A| \;$, где $A \; = \; arg \max\limits_{S \in V}(odd(G \setminus S) \; - \; |S|) \;$. Разность $odd(G \setminus A) \; - \; |A| \;$ имеет ту же четность, что и $n$, и $odd(H \setminus S) \; = \; 1 \;$, поэтому $|V_H|$ четно, значит, по лемме, мощность $S$ нечетна, следовательно она не равна нулю, значит, $1 \leq |S|$. Если $W \subset S \;$, то $odd(H \setminus S) \; = \; odd(G \setminus (S \cap V)) \; = odd(G \setminus (S \cap V)) \; - \; |S \cap V| \; + \; |S \cap V| \; \leq \; |S \cap V| \; + \; k \leq |S| \;$, так как $\max\limits_{S \in V}(odd(G \setminus S) - |S|) = k \;$. Таким образом, для графа $H$ выполнено условие теоремы Татта, следовательно в нём есть полное паросочетание. Рассмотрим полное паросочетание в графе $H$, удалим вершины $W$ из графа $H$. Количество непокрытых вершин после удаления не больше, чем количество удаленных вершин $k$, значит, $def(G) \; \leq \; k$. Удалим множество вершин $A \; = \; arg \max\limits_{S \in V}(odd(H \setminus S) \; - \; |S|) \;$ из графа $G\;$. Заметим, что после удаления в графе осталось $odd(G \setminus A)\;$ нечетных компонент и образовались новые непокрытые вершины, но при этом число нечетных компонент больше числа удаленных на $k$. Значит, хотя бы $k$ нечетных компонент содержали исходно непокрытую вершину, следовательно $def(G) \; \geq \; k \;$. Из $def(G) \; \leq \; k$ и $def(G) \; \geq \; k \;$ следует $def(G) \; = \; k \;$.

$\triangleleft$

Теорема (Татта-Бержа):

Дан граф $G$, размер максимального паросочетания в нем равен: $\mathrm{\alpha}(G) = \min\limits_{U \in V} \{\dfrac{1}{2}(|V|+|U|-\mathrm{odd}(G - U)\}.$

Доказательство:

$\triangleright$

Предположим $G$ — связный, иначе мы можем применить индукцию к компонентам $G$. Приведем доказательство по индукции по числу вершин в графе. База индукции: Очевидно, для $n = 1$ утверждение верно. Индукционный переход: Рассмотрим два случая: $G$ — содержит вершину $v$ покрытую всеми максимальными паросочетаниями (например средняя вершина) Тогда $\mathrm{\alpha}(G - v) = \mathrm{\alpha}(G) - 1$. По индукции, формула Татта-Берджа содержит $G - v$ для некоторого множества $U'$. Пусть $U = U' \bigcup v$. Тогда: $\mathrm{\alpha}(G) = \mathrm{\alpha}(G - v) + 1 = \dfrac{1}{2}(|V - v|+|U - v| - \mathrm{odd}(G - v - (U - v))) + 1 =$ $= \dfrac{1}{2}(|V| - 1 + |U|- 1 - \mathrm{odd}(G - U)) + 1 = \dfrac{1}{2}(|V|+|U| - \mathrm{odd}(G - U)).$ Для каждой вершины $v$ есть максимальное паросочетание $M$ которое не покрывает $v$ (например $C_3$) Покажем, что существует паросочетание размера $\dfrac{1}{2}(|V| - 1)$, из которого следует теорема (при $U = \emptyset$). От противного: Предположим что любое максимальная паросочетание $M$ не покрывает, по крайней мере, две различные вершины $u$ и $v$. Среди всех таких $(M, u, v)$ выберем их так, что $\mathrm{d}(u, u)$ в $G$ — минимально. Если $\mathrm{d}(u, u) = 1$, то $u$ и $v$ являются смежными, и, следовательно, мы можем увеличить $M$, что противоречит его максимальности. Значит $\mathrm{d}(u, u) \geqslant 2$, и, следовательно, мы можем выбрать промежуточную вершину $t$ на пути $u-v$ и $N$ максимальное паросочетание, такое что симметрическая разность с $M$ минимальна. Так как $(M, u, v)$ минимально, то $N$ должно охватывать $u$ и $v$ так, что есть другая вершина $x$, покрытая только в $M$. Пусть $y$ будет вершиной покрытой с $x$ в $M$ и заметим $y \neq t$ (иначе можно было бы добавить к $N$). Пусть $z$ будет вершиной покрытой с $y$ в $N$ и заметим $z \neq x$ (так как $x$ не покрыто в $N$). Тогда $N - yz + xy$ — паросочетание, которое имеет с $M$ меньшую симметрическую разность, что противоречит выбору $N$.

$\triangleleft$

Определение:

Множество $S \subset V (G)$, для которого $\mathrm{odd}(G - S) - |S| = \mathrm{def}(G)$, называется барьером (англ. barrier).

Определение:

Пусть $X \subset V$. Множeство соседей (англ. neighbors) $X$ определим формулой: $N(X)= \{ y \in V:(x,y) \in E \}$

Структурная теорема Эдмондса-Галлаи

Определение:

Структурные единицы декопозиции:

1. $D(G) = \{v \in V \mid$ существует максимальное паросочетание, не покрывающее $v\}$
2. $A(G) = N(D(G)) \setminus D(G)$
3. $C(G) = V \setminus(D(G) \bigcup A(G))$
4. $\alpha (G)$ — размер максимального паросочетания в $G.$

Пример. Рёбра из паросочетания выделены красным

Определение:

Граф $G$ называется фактор-критическим (англ. factor-critical graph), если для любой вершины $v \in G$ в графе $G \setminus {v}$ существует совершенное паросочетание.

Теорема (Галлаи):

$G$ — фактор-критический граф $\Leftrightarrow$ $G$ — связен и для любой вершины $u \in V(G)$ выполняется равенство $\alpha (G - u) = \alpha (G)$.

Лемма (Галлаи, о стабильности (англ. stability lemma)):

Пусть $a \in A(G).$ Тогда: $D(G - a) = D(G)$ $A(G - a) = A(G) \setminus \{a\}$ $C(G - a) = C(G)$ $\alpha (G - a) = \alpha (G) - 1.$

Доказательство:

$\triangleright$

Для начала докажем, что $D(G - a) = D(G)$. Случай а Случай b Случай c Покажем, что $D(G - a) \supset D(G)$ : Пусть $u \in D(G)$. Тогда существует максимальное паросочетание $M_u$ графа $G$, не покрывающее $u$. Поскольку любое максимальное паросочетание графа $G$ покрывает $a$, то $\alpha (G - a) = \alpha (G) - 1$ и более того, если, для некоторой вершины $x \in D(G)$, $ax \in M_u$, то $M_u \setminus {ax}$ — максимальное паросочетание графа $G - a$, не покрывающее $u$. Таким образом, $D(G - a) \supset D(G)$. покажем, что $D(G - a) \subset D(G)$: Предположим, что существует максимальное паросочетание $M'$ графа $G - a$, не покрывающее вершину $v$ $\notin D(G)$. Пусть $w \in D(G)$ — смежная с $a \in A(G)$ вершина, а $M_w$ — максимальное паросочетание графа $G$, не покрывающее $w$. Так как $v$ $\notin D(G)$, максимальное паросочетание $M_w$ покрывает вершину $v$. Рассмотрим граф $H = G(M_w \bigcup M')$ — очевидно, он является объединением нескольких путей и чётных циклов. Пусть $U$ — компонента связности графа $H$, содержащая $v$. Так как $deg_H(v) = 1$ (степень вершины), то $P = H(U)$ — путь с началом в вершине $v$. В пути $P$ чередуются рёбра из $M_w$ и $M'$, причём начинается путь ребром из $M_w$. Так как $deg_H(a) = 1$, то вершина a либо не принадлежит пути $P$, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию $M_w$). Рассмотрим несколько случаев: a. Путь $P$ кончается ребром из $M'$ (см. рисунок) Рассмотрим паросочетание $M_v = M_w \oplus E(P)$ (симметрическая разность $M_w$ и $E(P)$. то есть, рёбра, входящие ровно в одно из двух множеств). Очевидно, $M_v$ — максимальное паросочетание графа $G$, не покрывающее $v$, поэтому $v \in D(G)$, противоречие. b. Путь $P$ кончается ребром из $M_w$, вершина $a$ — конец пути $P$. (см.рисунок) Рассмотрим паросочетание $M_v∗ = (M_w \oplus E(P)) \bigcup \{aw\}$. Тогда $M_v∗$ — максимальное паросочетание графа $G$, не покрывающее $v$, поэтому $v \in D(G)$, противоречие. c. Путь $P$ кончается ребром из $M_w, a \in V(P)$ (см. рисунок) Рассмотрим паросочетание $M'' = M \oplus E(P)$. Тогда $|M''| = |M'| + 1$, причём $M'' \subset E(G - a)$. Противоречие с максимальностью паросочетания $M'$. Таким образом, наше предположение невозможно и $D(G - a) \subset D(G)$. А значит, $D(G - a) = D(G)$. Так как $D(G - a) = D(G)$, то все вершины, которые были соседями $D(G)$, таковыми и остались. Однако, по условию $a \in A(G)$, значит $A(G - a) = A(G) \setminus \{a\}$. Так же заметим, что $C(G - a) = V(G - a) \setminus (D(G - a) \cup A(G - a)) = V(G - a) \setminus (D(G) \cup (A(G) \setminus \{a\}))$$= V(G) \setminus (D(G) \cup A(G)) = C(G)$ Наконец, так как $a \in A(G)$, то все максимальные паросочетания в $G$ включали $a$. Следовательно, $\alpha (G - a) \lt \alpha (G)$. Заметим, что, взяв любое максимальное паросочетания в $G$ и удалив ребро инцидентное $a$, мы получим паросочетание $M'$, которое на 1 меньше исходного, при этом $M' \in E(G - a)$. В свою очередь, это самое большое паросочетание, которое мы могли теоретически получить в $G - a$. Следовательно, $\alpha (G - a) = \alpha (G) - 1.$

$\triangleleft$

Теорема (Галлаи, Эдмондс):

Пусть $G$ — граф, $U_1\ldots U_n$ — компоненты связности графа $G(D(G))$, $D_i = G(U_i), C = G(C(G))$. Тогда: Граф $C$ имеет совершенное паросочетание. Графы $D_1\ldots D_n$ — фактор-критические. Любое максимальное паросочетание $M$ графа $G$ состоит из совершенного паросочетания графа $C$, почти совершенных паросочетаний графов $D_1\ldots D_n$ и покрывает все вершины множества $A(G)$ рёбрами с концами в различных компонентах связности $U_1\ldots U_n.$ $\mathrm{def}(G) = n - |A(G)|.$ $2\mathrm{\alpha}(G) = v(G) + |A(G)| - n$.

Доказательство:

$\triangleright$

Пример Последовательно удаляя вершины множества $A = A(G)$, по лемме о стабильности мы получим: $D(G - A) = D(G),$ $A(G - A) = \O,$ $C(G - A) = C(G),$ $\alpha (G - A) = \alpha (G) - |A|.$ Это означает, что не существует рёбер, соединяющих вершины из $C(G - A)$ и $D(G - A)$. Каждое максимальное паросочетание $M'$ графа $G - A$ покрывает все вершины множества $C(G)$, поэтому $M'$ содержит совершенное паросочетание графа $C$. Тем самым, мы доказали пункт $1)$. Из формулы $\alpha(G - A) = \alpha (G) - |A|$ следует, что $U_1\ldots U_n$ — компоненты связности графа $G - A$. Для любой вершины $u \in U_i$ существует максимальное паросочетание $M_u$ графа $G - A$, не содержащее $u$. Так как $U_i$ — компонента связности графа $G - A$, паросочетание $M_u$ содержит максимальное паросочетание графа $D_i$ (разумеется, не покрывающее вершину $u$). Следовательно, $\alpha (D_i) = \alpha (D_i - u)$ и по теореме Галлаи (мы получаем, что граф $D_i$ — фактор-критический. Пусть $M$ — максимальное паросочетание графа $G$, а $M'$ получено из $M$ удалением всех рёбер, инцидентных вершинам множества $A$. Тогда $|M'| \geqslant |M| - |A|$ и по формуле $\alpha (G - A) = \alpha (G) - |A|$ понятно, что $M'$ — максимальное паросочетание графа $G - A$. Более того, из $\alpha (G - A) = \alpha (G) - |A|$ следует $|M'| = |M| - |A|$, а значит, все вершины множества $A$ покрыты в $M$ различными рёбрами. Так как $M'$ — максимальное паросочетание графа $G - A$, то по пунктам $1)$ и $2)$ очевидно, что $M'$ содержит совершенное паросочетание графа $C$ и почти совершенные паросочетания фактор-критических графов $D_1\ldots D_n$. Значит, рёбра паросочетания $M$ соединяют вершины $A$ с непокрытыми $M'$ вершинами различных компонент связности из $U_1\ldots U_n$. Из пункта $3)$ сразу же следуют равенства пункта $4)$ и $5)$.

$\triangleleft$

Утверждение (следствие из теоремы):

$A(G)$ — барьер графа $G$

Лемма (о связи барьера с $D(G)$):

Для любого барьера $B$ графа $G$ верно, что $B\cap D(G) = \varnothing$

Доказательство:

$\triangleright$

Рассмотрим $U_{1}, U_{2}, \ldots U_{n}$ — нечётные компоненты связанности $G \setminus B$, $\ M$ — максимальное паросочетание в $G$. $\forall\ U_{i}\ \exists x \in U_{i}: x$ не покрыта $\ M$ или $xv \in M \land v \in B$. Всего графе не покрыто хотя бы $odd(G\setminus B) - |B|$ вершин. Однако, так как $B$ — барьер, непокрыто ровно столько вершин. Следовательно, любое максимальное паросочетание не покрывает только вершины из $G \setminus B$, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из $D(G)$ не могла оказаться в барьере.

$\triangleleft$

Утверждение (Следствие из леммы):

В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами $G \setminus B$

$\triangleright$

Так как для барьера $B$ верно, что $odd(G\setminus B) - |B|=def(G) \geqslant 0$, то ровно $|B|$ вершин из нечётных компонент $G \setminus B$ покрыты рёбрами $xv \in M \land v \in B$

$\triangleleft$

Лемма (о дополнении барьера):

Пусть $x\in A(G)\cup C(G),\ G'=G\setminus x,\ B'$ — барьер графа $G'$. Тогда $B=B'\cup x$ — барьер графа $G$

Доказательство:

$\triangleright$

Так как $x \notin D(G)$, то для любого максимального паросочетания $M: x \in M$. Следовательно, $|M'| = |M| - 1$, где $M'$ — максимальное паросочетание в $G'$. $def(G') = (|V| - 1)- 2 \cdot |M'| = |V| - 2 \cdot |M| + 1 = def(G) + 1$ $odd(G - (B'\cup x)) = odd(G' - B') =$$|B'| + def(G') = |B'| + 1 + def(G) = |B'\cup x| + def(G)$ Отсюда следует, что $B$ — барьер графа $G$.

$\triangleleft$

Теорема (о структуре барьера):

Любой барьер графа состоит только из вершин $A(G)\cup C(G)$, причём каждая вершина из этого множества входит в какой-то барьер

Доказательство:

$\triangleright$

По лемме о связи барьера с $D(G)$ мы знаем, что в барьере нет вершин вершин из $D(G)$. По лемме о дополнение барьера мы можем взять любую вершину из $A(G)\cup C(G)$, удалить из графа, и с помощью барьера нового графа получить барьер исходного, включающий данную вершину.

$\triangleleft$

См. также

• Теорема Татта о существовании полного паросочетания
• Лапы и минимальные по включению барьеры в графе
• Пересечение всех максимальных по включению барьеров

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

• Edmonds-Gallai Decomposition and Factor-Critical Graphs
• Edmonds-Gallai Decomposition, Edmonds’ Algorithm
• — Лекция А.С. Станкевича