Изменения

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

Совершенное паросочетание в кубическом графе

1 байт добавлено, 22:04, 28 января 2016
м
Нет описания правки
*функция <tex>\mathtt{alternatingCycle}</tex> принимает три параметра: граф, совершенное паросочетание и ребро. Возвращает альтернативный цикл, включающий в себя данное ребро и обновляет совершенное паросочетание,
*функция <tex>\mathtt{reductions}</tex> сокращает граф,
*функция <tex>\mathtt{simpleReversion}</tex> восстанавливают восстанавливает граф,
*функция <tex>\mathtt{reductedGraph}</tex> принимает три параметра: граф, удаляемые вершины, добавляемые рёбра. Возвращает новый граф, у которого удалены выбранные вершины, вместе c инцидентными рёбрами и добавлены другие рёбра, переданные в параметрах. При этом исходный граф не меняется.
<tex>C =</tex> alternatingCycle<tex>(G, M, r[0])</tex>
<tex>M = M \oplus C</tex>
<tex>M = (M - r) \ \cup </tex> simpleReversion<tex>(G, v, w, r, M)</tex>
'''return''' <tex>M</tex>
84
правки

Навигация