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