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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition= <tex>o(G-U)</tex> - количество компонент связности нечетного размера в <tex> G...»)
 
Строка 14: Строка 14:
 
|definition=
 
|definition=
 
множество U, на котором достигается минимум в формуле Татта-Баржа назовем множеством свидетелей.}}
 
множество U, на котором достигается минимум в формуле Татта-Баржа назовем множеством свидетелей.}}
 +
 +
{{Утверждение
 +
|statement=
 +
выполняется следующее:
 +
* все вершины из U покрыты любим максимальным паросочетанием в G
 +
* если K - множество вершин компоненты G-U, тогда любое максимальное паросочетание в G покрывает как минимум половину вершин в K. В частности, каждая вершина в четной компоненте покрыта любым максимальным паросочетанием.
 +
}}
 +
 +
{{Утверждение
 +
|statement=
 +
если U - не пустое множество свидетелей Татта-Бержа для графа G, тогда в G есть вершины, которые входят в любое максимальное паросочетание.
 +
}}
 +
 +
{{Определение
 +
|definition=
 +
граф G = (V, E) называется фактор-критическим, если в нем нем полного паросочетания, но для каждой вершины v из V граф G-v имеет полное.}}
 +
 +
{{Теорема
 +
|statement=
 +
граф G факторо-критический тогда и только тогда, когда для каждой вершины v из V существует максимальное паросочетание в G, которое не покрывает вершину v.
 +
}}
 +
 +
{{Утверждение
 +
|statement=
 +
пусть C - цикл нечетной длины в G. Если граф G/С, полученный сжатием C в одну вершину, фактор-критический, то и G - фактор-критический.
 +
}}
 +
 +
=Декомпозиция Эдмондса-Галлаи=
 +
 +
{{Теорема
 +
|statement=
 +
дан граф 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>
 +
* U = A(G) - множество свидетелей Татта-Бержа
 +
* С(G) - объединение всех четных компонент G-A(G)
 +
* D(G) - объединение всех нечетных компонент G-A(G)
 +
* каждая компонента в G-A(G) - фактор-критическая
 +
|proof=
 +
лол.
 +
}}
 +
{{Утверждение
 +
|about=следствие из теоремы
 +
|statement=
 +
граф G фактор-критический тогда и только тогда, когда U не пусто и U - единственное множество свидетелей Татта-Бержа для G
 +
}}

Версия 20:57, 14 декабря 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 - фактор-критический.

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

Теорема:
дан граф G = (V, E). пусть:
  • [math]D(G) = {v из V| существуем максимальное паросочетание, не покрывающее v}[/math]
  • A(G) = N(D(G))\D(G)
  • C(G) = V\( D(G) or A(G) )


тогда:

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