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