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