Изменения
Нет описания правки
|[[Файл:Frinks_algorithm4.PNG|thumb|400px|Рисунок 4.]]
|}
==Алгоритм поиска совершенного паросочетания за O(n^2) (Frink's algorithm)==
*будем сокращать данный граф <tex>G</tex> вышеизложенным способом (на каждой итерации можем выбирать любое ребро) пока не удалим все вершины,
*когда все вершины закончились, создадим пустое совершенное паросочетание <tex>M</tex> и начнём обратный процесс для всех сокращений (начиная с последних удалённых вершин). Каждый такой шаг будет приводить к одному из четырёх базовых случаев, представленных в рисунке <tex>5</tex> или к одному из специальных случаев из рисунка <tex>6</tex>. Обратный процесс для всех специальных случаев, а так же для первых трёх базовых выполняется по строгому алгоритму, т.е. разрешим за <tex>O(1)</tex>.
