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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 42: Строка 42:
  
 
=Декомпозиция Эдмондса-Галлаи=
 
=Декомпозиция Эдмондса-Галлаи=
 +
 +
{{Определение
 +
|definition=
 +
необходимые определения:
 +
* <tex>D(G) = \{v \in V |</tex> существует максимальное паросочетание, не покрывающее <tex> v\}</tex>
 +
* <tex>A(G) = N(D(G)) \setminus D(G)</tex>
 +
* <tex>C(G) = V \setminus( D(G) \bigcup A(G) )</tex>
 +
* <tex> \alpha (G) </tex> - размер максимального паросочетания в <tex>G</tex>
 +
}}
 +
 +
{{Лемма
 +
|about= (Галлаи, о стабильности)
 +
|statement=
 +
пусть <tex> a \in A(G).</tex> Тогда:
 +
* <tex>D(G - a) = D(G)</tex>
 +
* <tex>A(G - a) = A(G) \setminus \{a\}</tex>
 +
* <tex>C(G - a) = C(G)</tex>
 +
* <tex> \alpha (G - a) = \alpha (G) - 1.</tex>
 +
|proof=
 +
много-много и с картинками. :(
 +
}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
дан граф G = (V, E). пусть:
+
пусть дан граф G = (V, E).
−
* <tex>D(G) = {v из V| существуем максимальное паросочетание, не покрывающее v}</tex>
 
−
* A(G) = N(D(G))\D(G)
 
−
* C(G) = V\( D(G) or A(G) )
 
 
<br>
 
<br>
−
тогда:
+
тогда:
 
<br>
 
<br>
−
* U = A(G) - множество свидетелей Татта-Бержа
+
* <tex> U = A(G) </tex> - множество свидетелей Татта-Бержа
−
* С(G) - объединение всех четных компонент G-A(G)
+
* <tex>С(G) </tex> - объединение всех четных компонент <tex>G - A(G)</tex>
−
* D(G) - объединение всех нечетных компонент G-A(G)
+
* <tex>D(G) </tex> - объединение всех нечетных компонент <tex>G - A(G)</tex>
−
* каждая компонента в G-A(G) - фактор-критическая
+
* каждая компонента в <tex> G - A(G)</tex> - фактор-критическая
 
|proof=
 
|proof=
−
лол.
+
1) A Последовательно удаляя вершины множества A = A(G)D по лемме о стабильности мы получим
 +
D(G − A) = D(G),
 +
A(G − A) = ∅,
 +
C(G − A) = C(G),
 +
α(G − A) = α(G) − |A|.
 +
Это означает, что не существует рјберD соединяющих вершины из C(G − A) и D(G − A). Каждое максимальное паросочетание M' графа G - A покрывает все вершины множества C(G), поэтому M' содержит
 +
совершенное паросочетание графа C. Тем самым, мы доказали пункт 1).
 +
 
 +
2) Из формулы α(G − A) = α(G) − |A|. следуетD что U1,..,Un- компоненты связности графа G − A. Для любой вершины u \in Ui существует максимальное
 +
 
 +
паросочетание Mu графа G - A, не содержащее u. Так как Ui -  компонента связности графа G - A, паросочетание Mu содержит максимальное паросочетание графа Di (разумеетсяD не покрывающее вершину u). Следовательно, α(Di) = α(Di - u) и по теореме 2.12 мы получаем, что граф Di - фактор-критический.
 +
 
 +
3) Пусть M - максимальное паросочетание графа G, а M' получено
 +
из M удалением всех рёбер, инцидентных вершинам множества A. Тогда
 +
|M'| ≥ |M| − |A| и по формуле α(G − A) = α(G) − |A| понятно, что M' - максимальное
 +
паросочетание графа G − A. Более того, из α(G − A) = α(G) − |A| следует |M'| = |M|−|A|, а значит, все вершины множества A покрыты в M различными рёбрамию Так как M' - максимальное паросочетание графа G - A, то по пунктам 1) и 2) очевидно, что M' содержит совершенное паросочетание графа C и почти совершенные паросочетания фактор-критических графов D1,...,Dn. Значит, рёбра паросочетания M соединяют вершины A с непокрытыми M' вершинами различных компонент
 +
связности из U1,...,Un.
 +
4) Из пункта 3) сразу же следуют оба равенства пункта 4
 +
 
 +
 
 
}}
 
}}
 +
 
{{Утверждение
 
{{Утверждение
 
|about=следствие из теоремы
 
|about=следствие из теоремы

Версия 16:24, 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] 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]
много-много и с картинками. :(
[math]\triangleleft[/math]
Теорема:
пусть дан граф G = (V, E).


тогда:

  • [math] U = A(G) [/math] - множество свидетелей Татта-Бержа
  • [math]С(G) [/math] - объединение всех четных компонент [math]G - A(G)[/math]
  • [math]D(G) [/math] - объединение всех нечетных компонент [math]G - A(G)[/math]
  • каждая компонента в [math] G - A(G)[/math] - фактор-критическая
Доказательство:
[math]\triangleright[/math]

1) A Последовательно удаляя вершины множества A = A(G)D по лемме о стабильности мы получим D(G − A) = D(G), A(G − A) = ∅, C(G − A) = C(G),

α(G − A) = α(G) −
[math]\triangleleft[/math]
Утверждение (следствие из теоремы):
граф G фактор-критический тогда и только тогда, когда U не пусто и U - единственное множество свидетелей Татта-Бержа для G
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Декомпозиция_Эдмондса-Галлаи&oldid=34208»