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

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

[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, на котором достигается минимум в формуле Татта-Баржа назовем множеством свидетелей.