Изменения

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

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

644 байта добавлено, 19:40, 14 декабря 2013
Новая страница: «{{Определение |definition= <tex>o(G-U)</tex> - количество компонент связности нечетного размера в <tex> G...»
{{Определение
|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, на котором достигается минимум в формуле Татта-Баржа назовем множеством свидетелей.}}
Анонимный участник

Навигация