Изменения

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

Алгоритм вырезания соцветий

18 байт добавлено, 05:43, 22 января 2011
Паросочетание в недвудольном графе
{{Определение
|definition= '''Соцветие ''' <tex>B</tex> графа <tex>G=(V,E)</tex> - цикл, состоящий из <tex>2k + 1</tex> ребер. }}
{{Определение
|definition= '''Cжатие соцветия ''' - граф <tex>G'</tex>, полученный из <tex>G</tex> сжатием всего нечётного цикла в одну псевдо-вершину (соответственно, все рёбра, инцидентные вершинам этого цикла, становятся инцидентными псевдо-вершине).}}
{{Определение
|definition= '''База соцветия ''' - вершина соцветия, в которую входит ребро не из данного соцветия.}}
== Теорема Эдмондса ==
Анонимный участник

Навигация