Изменения

Перейти к: навигация, поиск

Алгоритм Куна для поиска максимального паросочетания

557 байт убрано, 17:30, 11 января 2015
→‎Время работы
==Время работы==
:Итак, алгоритм Куна можно представить как серию из <tex>n_1n</tex> запусков обхода в глубину на всём графе.
:Следовательно, всего этот алгоритм исполняется за время <tex>O(nm)</tex>, где <tex>m</tex> {{---}} количество ребер, что в худшем случае есть <tex>O(n^3)</tex>.
:Более точная оценка:
:В описанной выше реализации запуски обхода в глубину/ширину происходят только из вершин первой доли, поэтому весь алгоритм исполняется за время <tex>O(n_1m)</tex> , где <tex>n_1</tex> — число вершин первой доли. В худшем случае это составляет <tex>O(n_1^2n_2)</tex>, где <tex>n_2</tex> — число вершин второй доли.
==Ссылки==
Freemahn
25
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/44161»

Навигация