Паросочетание: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Jumpow (обсуждение | вклад) |
Jumpow (обсуждение | вклад) Добавлена ссылка |
||
Строка 80:
| страницы= 248–255
| издание = [[Symposium on Foundations of Computer Science|Proc. 45th IEEE Symp. Foundations of Computer Science]]
| год = 2004}}</ref>, что в теории лучше для достаточно [[Плотный граф|плотных графов]], но на практике алгоритм медленнее.<ref>{{статья
| автор = Bala G. Chandran, Dorit S. Hochbaum
| arxiv = 1105.1569
| quote = the theoretically efficient algorithms listed above tend to perform poorly in practice
| заглавие = Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm
| год = 2011}}.</ref>
=== Во взвешенном двудольном графе ===
Во [[Глоссарий теории графов#взвешенный граф|взвешенном]] двудольном графе каждому ребру приписывается вес. '''Паросочетание максимального веса в двудольном графе'''<ref name="Wes01" /> определяется как паросочетание, для которого сумма весов рёбер паросочетания имеет максимальное значение. Если граф не является [[Полный двудольный граф|полным двудольным]], отсутствующие рёбра добавляются с нулевым весом. Задача поиска такого паросочетания известна как [[задача о назначениях]]. Она может быть решена с помощью модифицированного поиска [[Задача о кратчайшем пути|кратчайшего пути]] в алгоритме пополняющего пути.
Если используется [[алгорим Беллмана–Форда]], время работы будет <math>O(V^2 E)</math>, или цену ребра можно сдвинуть для достижения времени <math>O(V^2 \log{V} + V E)</math> при применении [[Алгоритм Дейкстры|алгоритма Дейкстры]] с [[Фибоначчиева куча|Фибоначчиевой кучей]]<ref name="Fredman87">{{статья
| |||