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

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

[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