Паросочетание: различия между версиями

=== Во взвешенном двудольном графе ===

Во [[Глоссарий теории графов#взвешенный граф|взвешенном]] двудольном графе каждому ребру приписывается вес. '''Паросочетание максимального веса в двудольном графе'''<ref name="Wes01" /> определяется как паросочетание, для которого сумма весов рёбер паросочетания имеет максимальное значение. Если граф не является [[Полный двудольный граф|полным двудольным]], отсутствующие рёбра добавляются с нулевым весом. Задача поиска такого паросочетания известна как [[задача о назначениях]]. Замечательный [[венгерский алгоритм]] решает задачу о назначениях и был одним из первых алгоритмов комбинаторной оптимизации. Задача может быть решена с помощью модифицированного поиска [[Задача о кратчайшем пути|кратчайшего пути]] в алгоритме пополняющего пути.

| автор= M. Fredman, R. Tarjan

| заглавие= Fibonacci heaps and their uses in improved network optimization algorithms

| место = Philadelphia

| год = 2009

}} глава 4.1.3 Historical notes, books, and surveys, глава 4.4.3 Efficient implementations

</ref>