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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Структурная теорема Эдмондса-Галлаи)
(Структурная теорема Эдмондса-Галлаи)
Строка 73: Строка 73:
 
Пусть u \in D(G). Тогда существует максимальное паросочетание Mu графа G, не покрывающее u. Поскольку любое максимальное паросочетание графа G покрывает a, то α(G - a) = α(G) - 1 и более того, если ax \in Mu, то Mu \setminus {ax}  -  максимальное паросочетание графа G - a, не покрывающее u. Таким образом, D(G - a) \supset D(G). <br>
 
Пусть u \in D(G). Тогда существует максимальное паросочетание Mu графа G, не покрывающее u. Поскольку любое максимальное паросочетание графа G покрывает a, то α(G - a) = α(G) - 1 и более того, если ax \in Mu, то Mu \setminus {ax}  -  максимальное паросочетание графа G - a, не покрывающее u. Таким образом, D(G - a) \supset D(G). <br>
 
2)покажем, что D(G − a) /subset D(G): <br>
 
2)покажем, что D(G − a) /subset D(G): <br>
Предположим, что существует максимальное паросочетание M' графа G - a, не покрывающее вершину v not \in D(G). Пусть w \in D(G) - смежная с a \in A(G) вершина, а Mw - максимальное паросочетание графа G, не покрывающее w. Так как v not \in D(G), максимальное паросочетание Mw покрывает вершину v. Рассмотрим граф H = G(Mw \bigcup M')  - очевидно, он является объединением нескольких путей и чётных циклов. Пусть U - компонента связности графа H, содержащая v. Так как dH(v) = 1, то P = H(U) - путь с началом в вершине v. В пути P чередуются рёбра из Mw и M', причём начинается путь ребром из Mw. Так как dH(a) = 1, то вершина a либо не принадлежит пути P, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию Mw). Рассмотрим несколько случаев:
+
Предположим, что существует максимальное паросочетание M' графа G - a, не покрывающее вершину v not \in D(G). Пусть w \in D(G) - смежная с a \in A(G) вершина, а Mw - максимальное паросочетание графа G, не покрывающее w. Так как v not \in D(G), максимальное паросочетание Mw покрывает вершину v. Рассмотрим граф H = G(Mw \bigcup M')  - очевидно, он является объединением нескольких путей и чётных циклов. Пусть U - компонента связности графа H, содержащая v. Так как dH(v) = 1, то P = H(U) - путь с началом в вершине v. В пути P чередуются рёбра из Mw и M', причём начинается путь ребром из Mw. Так как dH(a) = 1, то вершина a либо не принадлежит пути P, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию Mw). Рассмотрим несколько случаев: <br>
a.
 
b.
 
c.
 
  
 +
'''a.''' Путь P кончается ребром из M' (см. рисунок)<br>
 +
Рассмотрим паросочетание Mv = Mw \oplus E(P) (симметрическая разность
 +
Mw и E(P). то есть, рёбра, входящие ровно в одно из двух множеств).
 +
Очевидно, Mv - максимальное паросочетание графа G, не покрывающее v, поэтому v \in D(G), противоречие. <br>
  
 +
'''b.''' Путь P кончается ребром из Mw, вершина a - конец пути P. (см.рисунок)<br>
 +
Рассмотрим паросочетание Mv∗ = (Mw \oplus E(P)) \bigcup \{aw\}. Тогда Mv∗ - максимальное паросочетание графа G, не покрывающее v, поэтому v \in D(G), противоречие.
  
 +
'''c.'''  Путь P кончается ребром из Mw, 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).
 
}}
 
}}
  

Версия 17:29, 15 декабря 2013

Определение:
[math]o(G-U)[/math] - количество компонент связности нечетного размера в [math] G[V-U][/math].


Теорема (Татта-Бержа):
дан граф [math]G[/math], размер максимального паросочетания в нем [math]v(G)[/math] равен: [math]v(G) = min(U in V)1/2(|V|-|U|-o(G-U)) [/math]


Определение:
множество U, на котором достигается минимум в формуле Татта-Баржа назовем множеством свидетелей.


Утверждение:
выполняется следующее:
  • все вершины из U покрыты любим максимальным паросочетанием в G
  • если K - множество вершин компоненты G-U, тогда любое максимальное паросочетание в G покрывает как минимум половину вершин в K. В частности, каждая вершина в четной компоненте покрыта любым максимальным паросочетанием.
Утверждение:
если U - не пустое множество свидетелей Татта-Бержа для графа G, тогда в G есть вершины, которые входят в любое максимальное паросочетание.


Определение:
граф G = (V, E) называется фактор-критическим, если в нем нем полного паросочетания, но для каждой вершины v из V граф G-v имеет полное.


Теорема:
граф G факторо-критический тогда и только тогда, когда для каждой вершины v из V существует максимальное паросочетание в G, которое не покрывает вершину v.
Утверждение:
пусть C - цикл нечетной длины в G. Если граф G/С, полученный сжатием C в одну вершину, фактор-критический, то и G - фактор-критический.

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

Определение:
необходимые определения:
  • [math]D(G) = \{v \in V |[/math] существует максимальное паросочетание, не покрывающее [math] v\}[/math]
  • [math]A(G) = N(D(G)) \setminus D(G)[/math]
  • [math]C(G) = V \setminus( D(G) \bigcup A(G) )[/math]
  • [math] \alpha (G) [/math] - размер максимального паросочетания в [math]G[/math]


Теорема (Галлаи):
[math]G[/math] - фактор-критический граф [math] \Leftrightarrow [/math]
[math]G[/math] - связен и для любой вершины[math] u \in V(G) [/math] выполняется равенство [math] \alpha (G - u) = \alpha (G)[/math].
Лемма (Галлаи, о стабильности):
пусть [math] a \in A(G).[/math] Тогда:
  • [math]D(G - a) = D(G)[/math]
  • [math]A(G - a) = A(G) \setminus \{a\}[/math]
  • [math]C(G - a) = C(G)[/math]
  • [math] \alpha (G - a) = \alpha (G) - 1.[/math]
Доказательство:
[math]\triangleright[/math]

много-много и с картинками. :( Достаточно доказать, что D(G-a) = D(G).
1) покажем, что D(G − a) /supset D(G):
Пусть u \in D(G). Тогда существует максимальное паросочетание Mu графа G, не покрывающее u. Поскольку любое максимальное паросочетание графа G покрывает a, то α(G - a) = α(G) - 1 и более того, если ax \in Mu, то Mu \setminus {ax} - максимальное паросочетание графа G - a, не покрывающее u. Таким образом, D(G - a) \supset D(G).
2)покажем, что D(G − a) /subset D(G):
Предположим, что существует максимальное паросочетание M' графа G - a, не покрывающее вершину v not \in D(G). Пусть w \in D(G) - смежная с a \in A(G) вершина, а Mw - максимальное паросочетание графа G, не покрывающее w. Так как v not \in D(G), максимальное паросочетание Mw покрывает вершину v. Рассмотрим граф H = G(Mw \bigcup M') - очевидно, он является объединением нескольких путей и чётных циклов. Пусть U - компонента связности графа H, содержащая v. Так как dH(v) = 1, то P = H(U) - путь с началом в вершине v. В пути P чередуются рёбра из Mw и M', причём начинается путь ребром из Mw. Так как dH(a) = 1, то вершина a либо не принадлежит пути P, либо является её концом (в этом случае последнее ребро пути принадлежит паросочетанию Mw). Рассмотрим несколько случаев:

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

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

c. Путь P кончается ребром из Mw, a \in V(P) (см. рисунок)

Рассмотрим паросочетание M = M \oplus E(P). Тогда
[math]\triangleleft[/math]
Теорема (Галлаи, Эдмондс):
пусть дан граф G = (V, E).


тогда:
1) [math] U = A(G) [/math] - множество свидетелей Татта-Бержа
2) [math]С(G) [/math] - объединение всех четных компонент [math]G - A(G)[/math]
3) [math]D(G) [/math] - объединение всех нечетных компонент [math]G - A(G)[/math]

4) каждая компонента в [math] G - A(G)[/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]U1,{...},Un[/math]- компоненты связности графа [math]G - A[/math]. Для любой вершины [math]u \in Ui [/math]существует максимальное паросочетание [math]Mu[/math] графа [math]G - A[/math], не содержащее [math]u[/math]. Так как [math]Ui[/math] - компонента связности графа [math]G - A[/math], паросочетание [math]Mu[/math] содержит максимальное паросочетание графа [math]Di[/math] (разумеется, не покрывающее вершину [math]u[/math]). Следовательно, [math] \alpha (Di) = \alpha (Di - u) [/math] и по теореме Галлаи(выше) мы получаем, что граф [math]Di[/math] - фактор-критический.

3) Пусть [math]M[/math] - максимальное паросочетание графа [math]G[/math], а [math]M'[/math] получено из [math]M[/math] удалением всех рёбер, инцидентных вершинам множества [math]A[/math]. Тогда [math]|M'| \ge |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]D1,{...},Dn[/math]. Значит, рёбра паросочетания [math]M[/math] соединяют вершины [math]A[/math] с непокрытыми [math]M'[/math] вершинами различных компонент связности из [math]U1,{...},Un[/math].

4) Из пункта 3) сразу же следуют оба равенства пункта 4).
[math]\triangleleft[/math]
Утверждение (следствие из теоремы):
граф G фактор-критический тогда и только тогда, когда U не пусто и U - единственное множество свидетелей Татта-Бержа для G