Изменения

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

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

10 байт добавлено, 23:24, 28 декабря 2013
Нет описания правки
{{Определение
|definition=
<tex>\mathrm{odd}(G)</tex> - количество [[Отношение связности, компоненты связности#def2|компонент связности]] нечетного размера в <tex> G</tex>.}}
{{Определение
{{Определение
|definition=
Граф <tex>G</tex> называется '''фактор-критическим''' (англ. ''factor-critical graph''), если для любой вершины <tex>v \in G</tex> в графе <tex>G \setminus {v}</tex> существует [[Теорема Холла#def1|совершенное паросочетание]].
}}
|statement=
<tex>G</tex> - фактор-критический граф <tex> \Leftrightarrow </tex> <br>
<tex>G</tex> - связен и для любой вершины<tex> u \in V(G) </tex> выполняется равенство <tex> \alpha (G - u) = \alpha (G)</tex>.
}}
496
правок

Навигация