Изменения

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

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

11 байт добавлено, 20:09, 1 января 2014
Нет описания правки
'''a.''' Путь <tex>P</tex> кончается ребром из <tex> M'</tex> (см. рисунок)<br>
Рассмотрим паросочетание <tex>M_v = M_w \oplus E(P)</tex> (симметрическая разность
<tex> M_w </tex> и <tex>E(P)</tex>. то есть, рёбра, входящие ровно в одно из двух множеств).
Очевидно, <tex>M_v</tex> - максимальное паросочетание графа <tex>G</tex>, не покрывающее <tex>v</tex>, поэтому <tex> v \in D(G)</tex>, противоречие. <br>
497
правок

Навигация