Изменения

Перейти к: навигация, поиск

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

573 байта убрано, 22:15, 15 декабря 2013
Нет описания правки
{{Определение
|definition=
<tex>o(G-U)</tex> - количество компонент связности нечетного размера в <tex> G[V-U]</tex>.}} {{Теорема|about=Татта-Бержа|statement=дан граф <tex>G</tex>, размер максимального паросочетания в нем <tex>v(G)</tex> равен:<tex>v(G) = min(U in V)1/2(|V|-|U|-o(G-U)) </tex>}} 
{{Определение
|definition=
множество U'''Дефицитом''' графа G мы будем называть величину: <br><tex>def(G) = V(G) - 2\alpha (G)</tex>, на котором достигается минимум <br>где <tex>\alpha (G)</tex> - размер максимального поросочетания в формуле Татта<tex>G</tex>, а <br><tex>V(G)</tex> -Баржа назовем множеством свидетелей.множество вершин графа <tex>G</tex>}}
{{Утверждение
|statement=
выполняется следующее:
* все вершины из U покрыты любим максимальным паросочетанием в G
* если K - множество вершин компоненты G-U, тогда любое максимальное паросочетание в G покрывает как минимум половину вершин в K. В частности, каждая вершина в четной компоненте покрыта любым максимальным паросочетанием.
}}
{{УтверждениеТеорема|about=Бержа
|statement=
если U - не пустое множество свидетелей Татта-Бержа для любого графа G, тогда в выполняется:<br><tex>def(G) = max_{S \subset V(G)} \{o(G есть вершины, которые входят в любое максимальное паросочетание- S) - |S|\}.</tex>
}}
{{Определение
|definition=
граф G = (V, E) называется фактор-критическим, если в нем нем полного паросочетания, но для каждой вершины v из V граф G-v имеет полное.}}
{{Теорема
|about=Татта-Бержа
|statement=
дан граф <tex>G факторо-критический тогда и только тогда</tex>, когда для каждой вершины v из размер максимального паросочетания в нем равен:<br><tex>\alpha (G) = min_{U \in V существует максимальное паросочетание в } \{1/2(|V|-|U|-o(G, которое не покрывает вершину v.-U)\} </tex>
}}
 {{УтверждениеОпределение |statementdefinition=пусть C - цикл нечетной длины в G. Если граф Множество <tex>S \subset V (G)</С, полученный сжатием C в одну вершинуtex>, фактор-критический, то и для которого <tex>o(G - факторS) -критический|S| = def(G) </tex> называется '''барьером'''.
}}
 
 
=Структурная теорема Эдмондса-Галлаи=
|about = Галлаи, Эдмондс
|statement=
Для Пусть G - граф, <tex>U1,{...},Un</tex> - компоненты связности графа <tex> G (D(G))</tex> , <tex>Di = G(VUi), EC = G(C(G))</tex> выполняется. тогда: 1) Граф <tex>C</tex> имеет совершенное паросочетание.<br>2) Графы <tex>D1,{...},Dn</tex> - фактор-критические. <br>3) Любое максимальное паросочетание <tex>M</tex> графа <tex>G</tex> состоит из совершенного паросочетания графа <tex>C</tex>, почти совершенных паросочетаний графов <tex>D1,{...},Dn</tex> и покрывает все вершины множества <tex>A(G)</tex> рёбрами с концами в различных компонентах связности <tex>U1,{...},Un</tex> <br>4) <tex>def(G) = n - |A(G)|, 2\alpha (G) = v(G) + |A(G)| - n</tex>.
<tex>1) U = A(G) </tex> - множество свидетелей Татта-Бержа <br>
<tex>2) С(G) </tex> - объединение всех четных компонент <tex>G - A(G)</tex> <br>
<tex>3) D(G) </tex> - объединение всех нечетных компонент <tex>G - A(G)</tex> <br>
<tex>4)</tex> каждая компонента в <tex> G - A(G)</tex> - фактор-критическая
|proof=
1) Последовательно удаляя вершины множества<tex> A = A(G)</tex>, по лемме о стабильности мы получим:
|about=следствие из теоремы
|statement=
граф <tex>A(G фактор)</tex> -критический тогда и только тогда, когда U не пусто и U - единственное множество свидетелей Татта-Бержа для '''барьер''' графа <tex>G</tex>
}}
 
 
== Источники ==
*[http://www.people.vcu.edu/~dcranston/691/edmonds-gallai.pdf Edmonds-Gallai Decomposition and Factor-Critical Graphs]
*[http://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Д.В Карпов - теория графов]
 
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о паросочетании]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/34234»

Навигация