Изменения

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

1 байт добавлено, 18:04, 17 декабря 2013

Нет описания правки

|about=Бержа

|statement=

~~для~~ Для любого графа G выполняется:<br>

<tex>def(G) = max_{S \subset V(G)} \{o(G - S) - |S|\}.</tex>

}}

|about=Татта-Бержа

|statement=

~~дан~~ Дан граф <tex>G</tex>, размер максимального паросочетания в нем равен:<br>

<tex>\alpha (G) = min_{U \in V} \{1/2(|V|-|U|-o(G-U)\} </tex>

}}

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

|definition=

Множество <tex>S \subset V (G)</tex>, для которого <tex>o(G - S) - |S| = def(G) </tex> , называется '''барьером'''.

}}

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

|definition=

~~необходимые~~ Необходимые определения:

[[Файл: Edmonds-Gallai.png|300px|thumb|right|Пример. Рёбра из паросочетания выделены жирным]]

* <tex>D(G) = \{v \in V |</tex> существует максимальное паросочетание, не покрывающее <tex> v\}</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>

Анонимный участник