Википедия

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

Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Неактуальный шаблон
Неактуальные шаблоны и ошибочные ссылки
Строка 93:
=== Во взвешенном двудольном графе ===
Во [[Глоссарий теории графов#взвешенный граф|взвешенном]] двудольном графе каждому ребру приписывается вес. '''Паросочетание максимального веса в двудольном графе'''<ref name="Wes01" /> определяется как паросочетание, для которого сумма весов рёбер паросочетания имеет максимальное значение. Если граф не является [[Полный двудольный граф|полным двудольным]], отсутствующие рёбра добавляются с нулевым весом. Задача поиска такого паросочетания известна как [[задача о назначениях]]. Замечательный [[венгерский алгоритм]] решает задачу о назначениях и был одним из первых алгоритмов комбинаторной оптимизации. Задача может быть решена с помощью модифицированного поиска [[Задача о кратчайшем пути|кратчайшего пути]] в алгоритме пополняющего пути.
Если используется [[алгоритм Беллмана–ФордаБеллмана — Форда]], время работы будет <math>O(V^2 E)</math>, или цену ребра можно сдвинуть для достижения времени <math>O(V^2 \log{V} + V E)</math> при применении [[Алгоритм Дейкстры|алгоритма Дейкстры]] с [[Фибоначчиева куча|Фибоначчиевой кучей]]<ref name="Fredman87">{{статья
| автор= M. Fredman, R. Tarjan
| заглавие= Fibonacci heaps and their uses in improved network optimization algorithms
Строка 115:
{{Main|Алгоритм для паросочетаний Эдмондса}}
Имеется алгоритм полиномиального времени для нахождения наибольшего паросочетания или паросочетания максимального веса в графе, не являющемся двудольным. Следуя {{не переведено 5|Джек Эдмондс|Джеку Эдмондсу||Jack Edmonds}} его называют методом ''путей, деревьев и цветов'' или просто {{не переведено 5|Алгоритм Эдмондса для паросочетаний|алгоритмом Эдмондса для паросочетаний||Edmonds's matching algorithm}}. Алгоритм использует {{не переведено 5|Двунаправленный граф|двунаправленные дуги||bidirected graph}}.
Обобщение той же техники может быть использовано для поиска {{не переведено 5|[[Задача о независимом множестве – дополнить|максимального независимого множества||maximum independent set}}]] в [[Граф без клешней|графах без клешней]]. Алгоритм Эдмодса был впоследствии улучшен до времени работы <math>O(\sqrt{V}E)</math>, что соответствует алгоритмам для двудольных графов<ref>
{{статья
| автор = Silvio Micali, Vijay Vazirani
Строка 128:
Максимальное паросочетание можно найти простым жадным алгоритмом. Наибольшее паросочетание является также максимальным, и, поэтому, имеется возможность найти ''самое большое'' максимальное паросочетание за полиномиальное время. Однако неизвестно никакого полиномиального по времени алгоритма для нахождения '''наименьшего максимального паросочетания''', то есть максимального паросочетания, содержащего ''наименьшее возможное'' число рёбер.
 
Заметим, что наибольшее паросочетание из ''k'' рёбер является {{не[[Доминирующее переведеномножество 5|Рёберное доминирующее множестворёбер|рёберным доминирующим множеством||edge dominating set}}]] с ''k'' рёбрами. И обратно, если задано минимальное рёберное доминирующее множество с ''k'' рёбрами, мы можем построить наибольшее паросочетание с ''k'' рёбрами за полиномиальное время. Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества<ref>{{статья
| автор= Yannakakis Mihalis, Gavril Fanica
| заглавие=Edge dominating sets in graphs
Строка 214:
 
== Характеристики и замечания ==
[[Теорема Кёнига (комбинаторика)|Теорема Кёнига]] утверждает, что в двудольных графах наибольшее паросочетание равно размеру минимального [[Задача о вершинном покрытии|вершинного покрытия]]. Из этого следует, что для двудольных графов задачи нахождения минимального вершинного покрытия, [[МаксимальноеЗадача независимоео множествонезависимом множестве|максимального независимого множества]], и [[Максимальная вершинная биклика|максимальной вершинной биклики]] могут быть решены за [[Класс P|полиномиальное время]].
 
[[Теорема Холла]] (или теорема о свадьбах) обеспечивает характеризацию двудольных графов, имеющих совершенные паросочетания, а {{не переведено 5|Теорема Тутта|Теорема Тутта||Tutte theorem}} даёт характеризацию произвольных графов.
 
Совершенное паросочетание — это стягивающий [[Регулярный граф|1-регулярный]] подграф, то есть [[Факторизация графа|1-фактор]]. В общем случае, стягивающий ''k''-регулярный подграф — это [[Факторизация графа|''k''-фактор]].
 
== Приложения ==
Строка 238:
* [[Задача о независимом множестве|Независимое множество]]
* {{не переведено 5|Декомпозиция Дульмажа-Мендельсона|Декомпозиция Дульмажа-Мендельсона||Dulmage–Mendelsohn decomposition}}
* {{не[[Задача переведеноо 5марьяже|Устойчивое паросочетание|Устойчивое паросочетание||Stable matching}}]]
* {{не переведено 5|Оптимальное паросочетание|Оптимальное паросочетание||Optimal matching}}
* {{не переведено 5|Кососимметический граф|Кососимметический граф||Skew-symmetric graph}}
Источник — https://ru.wikipedia.org/wiki/Паросочетание