84
правки
Изменения
м
→Псевдокод алгоритма Фринка
*функция <tex>\mathtt{reductions}</tex> сокращает граф,
*функция <tex>\mathtt{simpleReversion}</tex> восстанавливают граф.
*функция <tex>\mathtt{reductedGraph}</tex> принимает три параметра: граф, удаляемые вершины, добавляемые рёбра. Возвращает новый граф, у которого удалены выбранные вершины, вместе инцидентными рёбрами и добавлены другие рёбра, переданные в параметрах. При этом исходный граф не меняется.
'''function''' frinkMatching<tex>(G)</tex>:
<tex>v - w = E[0]</tex>
<tex>R = </tex> reductions<tex>(G, v - w)</tex>
'''if''' bridgeless<tex>(reductedGraph(G[V - , \{v, w\}, E \cup R[0] ])</tex>
<tex>r = R[0]</tex>
'''else'''
<tex>r = R[1]</tex>
<tex>M =</tex> frinkMatching <tex>(reductedGraph(G[V - ,\{v, w\}, E \cup r])</tex>
'''if''' <tex>|r \cap M| = 2 </tex>
<tex>C =</tex> alternatingCycle<tex>(G, M, r[0])</tex>
