84
правки
Изменения
Нет описания правки
==Алгоритм поиска совершенного паросочетания за O(n^2) (Frink's algorithm)==
*будем сокращать данный граф <tex>G</tex> вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины,
*когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений , то есть восстановление графа (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Обратный процесс Восстановление для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешим за <tex>O(1)</tex>. Единственный проблемный случай, когда оба ребра принадлежат совершенному паросочетанию. В этой ситуации необходимо найти альтернативный цикл, содержащий как минимум одно из этих рёбер и обновить паросочетание с этим циклом. Эти действия сводят четвёртый базовый случай к одному из первых трёх.
'''return''' <tex>M</tex>
'''end if'''
==Время работы==
Операция сокращения должна на каждом шаге проверять граф на наличие мостов<tex>O(n)</tex>, кроме того, при возникновении четвёртого базового случая требуется найти альтернативный цикл за <tex>O(n)</tex>. В алгоритме <tex>O(n)</tex> операций сокращения и восстановления графа, причем каждая из этих операций требует <tex>O(n)</tex> времени. Таким образом, весь этот алгоритм исполняется за время <tex>O(n^2)</tex>.
