Декомпозиция Эдмондса-Галлаи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 145: Строка 145:
 
|about = о связи барьера с <tex>D(G)</tex>
 
|about = о связи барьера с <tex>D(G)</tex>
 
|statement= Для любого барьера графа <tex>B</tex> верно, что <tex>B\cap D(G) = \empty</tex>
 
|statement= Для любого барьера графа <tex>B</tex> верно, что <tex>B\cap D(G) = \empty</tex>
−
|proof= Рассмотрим <tex>U_{1}, U_{2},  \ldots U_{n}</tex> {{---}} нечётные компоненты связанности <tex>G \backslash B</tex>, <tex>\ M</tex> {{---}} максимальное паросочетание в <tex>G</tex>. <tex>\forall\ U_{i}\ \exists x \in U_{i}: x</tex> не покрыт <tex>\ M</tex>, или <tex>xv \in M \land v \in B</tex>. Всего графе не покрыто <tex>M</tex> хотя бы <tex>odd(G\backslash B) - |B|</tex> вершин. Однако так как <tex>B</tex> {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно любое максимальное паросочетание не покрывает только вершины из <tex>G \backslash B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.
+
|proof= Рассмотрим <tex>U_{1}, U_{2},  \ldots U_{n}</tex> {{---}} нечётные компоненты связанности <tex>G \setminus B</tex>, <tex>\ M</tex> {{---}} максимальное паросочетание в <tex>G</tex>. <tex>\forall\ U_{i}\ \exists x \in U_{i}: x</tex> не покрыт <tex>\ M</tex>, или <tex>xv \in M \land v \in B</tex>. Всего графе не покрыто <tex>M</tex> хотя бы <tex>odd(G\setminus B) - |B|</tex> вершин. Однако так как <tex>B</tex> {{---}} барьер, непокрыто '''ровно''' столько вершин. Следовательно любое максимальное паросочетание не покрывает только вершины из <tex>G \setminus B</tex>, а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из <tex>D(G)</tex> не могла оказаться в барьере.
 
}}
 
}}
  
 
{{Утверждение
 
{{Утверждение
 
|about=Следствие из леммы
 
|about=Следствие из леммы
−
|statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G \backslash B</tex>
+
|statement=В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами <tex>G \setminus B</tex>
−
|proof=Так в барьере <tex>odd(G\backslash B) - |B|=def(G) \geqslant 0</tex>, то ровно <tex>|B|</tex> вершин из нечётных компонент <tex>G \backslash B</tex> покрыты рёбрами <tex>xv \in M \land v \in B</tex>
+
|proof=Так в барьере <tex>odd(G\setminus B) - |B|=def(G) \geqslant 0</tex>, то ровно <tex>|B|</tex> вершин из нечётных компонент <tex>G \setminus B</tex> покрыты рёбрами <tex>xv \in M \land v \in B</tex>
 
}}
 
}}
 +
 +
{{Лемма
 +
|id = barier_struct2
 +
|about = о дополнении барьера
 +
|statement= Пусть <tex>x\in A(G)\cup C(G),\ G'=G\setminus x,\ B'</tex> {{---}} барьер графа <tex>G'</tex>. Тогда <tex>B=B'\cup x</tex> {{---}} барьер графа <tex>G</tex>
 +
|proof= Так как <tex>x \notin D(G)</tex>, то <tex>\forall\ M</tex> {{---}} максимального паросочетания в <tex>G : x \in M</tex>. Следовательно <tex>|M'| = |M| - 1</tex>, где <tex>M'</tex> {{---}} максимальное паросочетание в <tex>G'.\ def(G') = (|V| - 1)- 2 \cdot |M'| = |V| - 2 \cdot |M| + 1 = def(G) + 1</tex> <tex>odd(G - (B'\cup x)) = odd(G' - B') = |B'| + def(G') = |B'| + 1 + def(G) = |B'\cup x| + def(G) = |B| + def(G)</tex>
 +
Отсюда следует, что <tex>B</tex> {{---}} барьер графа <tex>G</tex>.
 +
}}
  
 
== См. также ==
 
== См. также ==

Версия 20:02, 14 декабря 2017

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

Определение:
Дефицитом (англ. deficit) графа [math]G[/math] мы будем называть величину:

[math]\mathrm{def}(G) = |V| - 2\alpha (G)[/math],
где [math]\alpha (G)[/math] — размер максимального паросочетания в [math]G[/math], а

[math]V(G)[/math] — множество вершин графа [math]G. [/math]


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


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

Предположим [math]G[/math] — связный, иначе мы можем применить индукцию к компонентам [math]G[/math]. Приведем доказательство по индукции по числу вершин в графе.
База индукции:
Очевидно, для [math] n = 1 [/math] утверждение верно.
Индукционный переход:
Рассмотрим два случая:

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


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


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

Определение:
Необходимые определения:
Пример. Рёбра из паросочетания выделены красным
  1. [math]D(G) = \{v \in V \mid [/math] существует максимальное паросочетание, не покрывающее [math] v\}[/math]
  2. [math]A(G) = N(D(G)) \setminus D(G)[/math]
  3. [math]C(G) = V \setminus(D(G) \bigcup A(G))[/math]
  4. [math] \alpha (G) [/math] — размер максимального паросочетания в [math] G. [/math]


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


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


Лемма (Галлаи, о стабильности (англ. stability lemma)):
Пусть [math] a \in A(G).[/math] Тогда:
  1. [math]D(G - a) = D(G)[/math]
  2. [math]A(G - a) = A(G) \setminus \{a\}[/math]
  3. [math]C(G - a) = C(G)[/math]
  4. [math] \alpha (G - a) = \alpha (G) - 1.[/math]
Доказательство:
[math]\triangleright[/math]

Достаточно доказать, что [math]D(G - a) = D(G)[/math].

Случай а
Случай b
Случай c
  1. покажем, что [math]D(G - a) \supset D(G)[/math] :
    Пусть [math]u \in D(G)[/math]. Тогда существует максимальное паросочетание [math]M_u[/math] графа [math]G[/math], не покрывающее [math]u[/math]. Поскольку любое максимальное паросочетание графа [math]G[/math] покрывает [math]a[/math], то [math] \alpha (G - a) = \alpha (G) - 1 [/math] и более того, если, для некоторой вершины [math]x \in D(G)[/math], [math]ax \in M_u[/math], то [math]M_u \setminus {ax} [/math] — максимальное паросочетание графа [math] G - a [/math], не покрывающее [math] u [/math]. Таким образом, [math]D(G - a) \supset D(G) [/math].
  2. покажем, что [math] D(G - a) \subset D(G)[/math]:

Предположим, что существует максимальное паросочетание [math]M'[/math] графа [math] G - a[/math], не покрывающее вершину [math]v[/math] [math] \notin D(G)[/math]. Пусть [math] w \in D(G) [/math] — смежная с [math] a \in A(G)[/math] вершина, а [math] M_w [/math] — максимальное паросочетание графа [math] G [/math], не покрывающее [math] w [/math]. Так как [math]v[/math] [math] \notin D(G) [/math], максимальное паросочетание [math] M_w [/math] покрывает вершину [math]v[/math]. Рассмотрим граф [math] H = G(M_w \bigcup M') [/math] — очевидно, он является объединением нескольких путей и чётных циклов. Пусть [math] U [/math] — компонента связности графа [math] H [/math], содержащая [math]v[/math]. Так как [math] deg_H(v) = 1 [/math] (степень вершины), то [math] P = H(U) [/math] — путь с началом в вершине [math]v[/math]. В пути [math]P[/math] чередуются рёбра из [math] M_w[/math] и [math]M' [/math], причём начинается путь ребром из [math]M_w [/math]. Так как [math] deg_H(a) = 1 [/math], то вершина a либо не принадлежит пути [math]P[/math], либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию [math] M_w[/math]). Рассмотрим несколько случаев:

a. Путь [math]P[/math] кончается ребром из [math] M'[/math] (см. рисунок)
Рассмотрим паросочетание [math]M_v = M_w \oplus E(P)[/math] (симметрическая разность [math] M_w[/math] и [math]E(P)[/math]. то есть, рёбра, входящие ровно в одно из двух множеств). Очевидно, [math]M_v[/math] — максимальное паросочетание графа [math]G[/math], не покрывающее [math]v[/math], поэтому [math] v \in D(G)[/math], противоречие.

b. Путь [math]P[/math] кончается ребром из [math] M_w[/math], вершина [math]a[/math] — конец пути [math]P[/math]. (см.рисунок)
Рассмотрим паросочетание [math]M_v∗ = (M_w \oplus E(P)) \bigcup \{aw\} [/math]. Тогда [math] M_v∗ [/math] — максимальное паросочетание графа [math] G [/math], не покрывающее [math] v [/math], поэтому [math] v \in D(G) [/math], противоречие.

c. Путь [math] P [/math] кончается ребром из [math] M_w, a \in V(P) [/math] (см. рисунок) Рассмотрим паросочетание [math] M'' = M \oplus E(P) [/math]. Тогда [math] |M''| = |M'| + 1 [/math], причём [math]M'' \subset E(G - a)[/math]. Противоречие с максимальностью паросочетания [math]M'[/math].

Таким образом, наше предположение невозможно и [math]D(G - a) \subset D(G)[/math].

А значит, [math]D(G - a) = D(G)[/math].
[math]\triangleleft[/math]


Теорема (Галлаи, Эдмондс):
Пусть [math]G[/math] — граф, [math]U_1\ldots U_n[/math] — компоненты связности графа [math]G(D(G))[/math], [math]D_i = G(U_i), C = G(C(G))[/math]. Тогда:
  1. Граф [math]C[/math] имеет совершенное паросочетание.
  2. Графы [math]D_1\ldots D_n[/math] — фактор-критические.
  3. Любое максимальное паросочетание [math]M[/math] графа [math] G [/math] состоит из совершенного паросочетания графа [math] C [/math], почти совершенных паросочетаний графов [math] D_1\ldots D_n [/math] и покрывает все вершины множества [math] A(G) [/math] рёбрами с концами в различных компонентах связности [math] U_1\ldots U_n. [/math]
  4. [math]\mathrm{def}(G) = n - |A(G)|.[/math]
  5. [math]2\mathrm{\alpha}(G) = v(G) + |A(G)| - n[/math].
Доказательство:
[math]\triangleright[/math]
Пример
  1. Последовательно удаляя вершины множества [math]A = A(G)[/math], по лемме о стабильности мы получим:
    • [math]D(G - A) = D(G),[/math]
    • [math]A(G - A) = \O, [/math]
    • [math]C(G - A) = C(G),[/math]
    • [math]\alpha (G - A) = \alpha (G) - |A|.[/math]
    Это означает, что не существует рёбер, соединяющих вершины из [math]C(G - A)[/math] и [math]D(G - A)[/math]. Каждое максимальное паросочетание [math]M'[/math] графа [math]G - A[/math] покрывает все вершины множества [math]C(G)[/math], поэтому [math]M'[/math] содержит совершенное паросочетание графа [math]C[/math]. Тем самым, мы доказали пункт 1).
  2. Из формулы [math] \alpha(G - A) = \alpha (G) - |A|[/math] следует, что [math]U_1\ldots U_n[/math] — компоненты связности графа [math]G - A[/math]. Для любой вершины [math]u \in U_i[/math] существует максимальное паросочетание [math]M_u[/math] графа [math]G - A[/math], не содержащее [math]u[/math]. Так как [math]U_i[/math] — компонента связности графа [math]G - A[/math], паросочетание [math]M_u[/math] содержит максимальное паросочетание графа [math]D_i[/math] (разумеется, не покрывающее вершину [math]u[/math]). Следовательно, [math] \alpha (D_i) = \alpha (D_i - u) [/math] и по теореме Галлаи (выше) мы получаем, что граф [math]D_i[/math] — фактор-критический.
  3. Пусть [math]M[/math] — максимальное паросочетание графа [math]G[/math], а [math]M'[/math] получено из [math]M[/math] удалением всех рёбер, инцидентных вершинам множества [math]A[/math]. Тогда [math]|M'| \geqslant |M| - |A|[/math] и по формуле [math] \alpha (G - A) = \alpha (G) - |A|[/math] понятно, что [math]M'[/math] — максимальное паросочетание графа [math]G - A[/math]. Более того, из [math] \alpha (G - A) = \alpha (G) - |A|[/math] следует [math]|M'| = |M| - |A|[/math], а значит, все вершины множества [math]A[/math] покрыты в [math]M[/math] различными рёбрами. Так как [math]M'[/math] — максимальное паросочетание графа [math]G - A[/math], то по пунктам 1) и 2) очевидно, что [math]M'[/math] содержит совершенное паросочетание графа [math]C[/math] и почти совершенные паросочетания фактор-критических графов [math]D_1\ldots D_n[/math]. Значит, рёбра паросочетания [math]M[/math] соединяют вершины [math]A[/math] с непокрытыми [math]M'[/math] вершинами различных компонент связности из [math]U_1\ldots U_n[/math].
  4. Из пункта 3) сразу же следуют равенства пункта 4) и 5).
[math]\triangleleft[/math]
Утверждение (следствие из теоремы):
[math]A(G)[/math] — барьер графа [math]G[/math]
Лемма (о связи барьера с [math]D(G)[/math]):
Для любого барьера графа [math]B[/math] верно, что [math]B\cap D(G) = \empty[/math]
Доказательство:
[math]\triangleright[/math]
Рассмотрим [math]U_{1}, U_{2}, \ldots U_{n}[/math] — нечётные компоненты связанности [math]G \setminus B[/math], [math]\ M[/math] — максимальное паросочетание в [math]G[/math]. [math]\forall\ U_{i}\ \exists x \in U_{i}: x[/math] не покрыт [math]\ M[/math], или [math]xv \in M \land v \in B[/math]. Всего графе не покрыто [math]M[/math] хотя бы [math]odd(G\setminus B) - |B|[/math] вершин. Однако так как [math]B[/math] — барьер, непокрыто ровно столько вершин. Следовательно любое максимальное паросочетание не покрывает только вершины из [math]G \setminus B[/math], а значит каждая вершина барьера покрыта в любом максимальном паросочетании. Отсюда получаем, что ни одна вершина из [math]D(G)[/math] не могла оказаться в барьере.
[math]\triangleleft[/math]
Утверждение (Следствие из леммы):
В любом максимальном паросочетании все вершины барьера соединены соединены с вершинами [math]G \setminus B[/math]
[math]\triangleright[/math]
Так в барьере [math]odd(G\setminus B) - |B|=def(G) \geqslant 0[/math], то ровно [math]|B|[/math] вершин из нечётных компонент [math]G \setminus B[/math] покрыты рёбрами [math]xv \in M \land v \in B[/math]
[math]\triangleleft[/math]
Лемма (о дополнении барьера):
Пусть [math]x\in A(G)\cup C(G),\ G'=G\setminus x,\ B'[/math] — барьер графа [math]G'[/math]. Тогда [math]B=B'\cup x[/math] — барьер графа [math]G[/math]
Доказательство:
[math]\triangleright[/math]

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

Отсюда следует, что [math]B[/math] — барьер графа [math]G[/math].
[math]\triangleleft[/math]

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Декомпозиция_Эдмондса-Галлаи&oldid=62645»