Максимальное соответствие весу

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Maximum weight matching" – news · newspapers · books · scholar · JSTOR (April 2024)

В информатике и теории графов задача о максимальном весовом паросочетании — это задача нахождения во взвешенном графе паросочетания , в котором сумма весов максимальна.

Частным случаем этого является задача назначения , в которой входные данные ограничены двудольным графом , а соответствие ограничено мощностью меньшего из двух разделов. Другим частным случаем является задача нахождения максимального мощностного соответствия на невзвешенном графе: это соответствует случаю, когда все веса ребер одинаковы.

Существует временной алгоритм для поиска максимального паросочетания или паросочетания максимального веса в графе, который не является двудольным; он принадлежит Джеку Эдмондсу , называется методом путей, деревьев и цветов или просто алгоритмом Эдмондса и использует двунаправленные ребра . Обобщение того же метода также может быть использовано для поиска максимальных независимых множеств в графах без клешней .${\displaystyle O(V^{2}E)}$

Существуют более сложные алгоритмы, обзор которых был сделан Дуаном и Петти ^[1] (см. Таблицу III). Их работа предлагает алгоритм приближения для задачи максимального соответствия весов, который выполняется за линейное время для любой фиксированной границы ошибки.

Эта статья по теории графов — заглушка . Вы можете помочь Википедии, расширив ее.

• v
• t
• e