Паросочетание

Максимальное паросочетание — это такое паросочетание M в графе G, которое не содержится ни в каком другом паросочетании этого графа, то есть к нему невозможно добавить ни одно ребро, которое бы являлось несмежным ко всем рёбрам паросочетания. Другими словами, паросочетание M графа G является максимальным, если любое ребро в G имеет непустое пересечение, по крайней мере, с одним ребром из M. Ниже приведены примеры максимальных паросочетаний (красные рёбра) в трёх графах[1].

Наибольшее паросочетание (или максимальное по размеру паросочетание[2])— это такое паросочетание, которое содержит максимальное количество рёбер. Число паросочетания[3] ${\displaystyle \nu (G)}$ графа ${\displaystyle G}$ — это число рёбер в наибольшем паросочетании. У графа может быть множество наибольших паросочетаний. При этом любое наибольшее паросочетание является максимальным, но не любое максимальное будет наибольшим. Следующие три рисунка показывают наибольшие паросочетания в тех же трёх графах[1].

Некоторые авторы используют термин «максимальное паросочетание» для наибольшего паросочетания[4][5][6][7].

Совершенным паросочетанием (или 1-фактором) называется паросочетание, в котором участвуют все вершины графа. То есть любая вершина графа инцидентна ровно одному ребру, входящему в паросочетание. Фигура (b) на рисунке выше является примером такого паросочетания. Любое совершенное паросочетание является наибольшим и максимальным. Совершенное паросочетание является также рёберным покрытием минимального размера. В общем случае ${\displaystyle \nu (G)\leq \rho (G)}$, где ${\displaystyle \rho (G)}$ — число рёберного покрытия графа ${\displaystyle G}$, иными словами, размер наибольшего паросочетания не превосходит размера наименьшего рёберного покрытия.

Почти совершенным паросочетанием называется паросочетание, в котором не участвует ровно одна вершина. Это может произойти, если граф имеет нечётное число вершин. На рисунке выше паросочетание в графе (c) является почти совершенным. Если для любой вершины в графе существует почти совершенное паросочетание, не содержащее именно эту вершину, граф называется факторно-критическим.

Пусть задано паросочетание M.

• чередующийся путь — это путь, в котором рёбра поочерёдно принадлежат паросочетанию и не принадлежат ему.
• пополняющий путь (или увеличивающий путь) — это чередующийся путь, начинающийся и кончающийся свободными вершинами (то есть не участвующими в паросочетании).

Лемма Бержа утверждает, что паросочетание является наибольшим в том и только в том случае, если не существует пополняющего пути.

Задачи нахождения паросочетания часто возникают при работе с двудольными графами. Поиск наибольшего паросочетания в двудольном графе[9] ${\displaystyle G=(V=(X,Y),E)}$ является, пожалуй, простейшей задачей. Алгоритм пополняющего пути получает его, находя пополняющий путь из каждой вершины ${\displaystyle x\in X}$ в ${\displaystyle Y}$ и добавляя его в паросочетание, если путь будет найден. Поскольку пополняющий путь может быть найден за время ${\displaystyle O(E)}$, время работы алгоритма будет ${\displaystyle O(VE)}$. Это решение эквивалентно добавлению суперисточника ${\displaystyle s}$ с рёбрами ко всем вершинам ${\displaystyle X}$, и суперстока ${\displaystyle t}$ с рёбрами из всех вершин ${\displaystyle Y}$, и поиску максимального потока из ${\displaystyle s}$ в ${\displaystyle t}$. Все рёбра, по которым идёт поток из ${\displaystyle X}$ в ${\displaystyle Y}$, образуют максимальное паросочетание. Несколько быстрее работает алгоритм Хопкрофта — Карпа, работающий за время ${\displaystyle O({\sqrt {V}}E)}$. Другой подход базируется на алгоритме быстрого умножения матриц и даёт сложность ${\displaystyle O(V^{2.376})}$[10], что в теории лучше для достаточно плотных графов, но на практике алгоритм медленнее.[11]

Во взвешенном двудольном графе каждому ребру приписывается вес. Паросочетание максимального веса в двудольном графе[9] определяется как паросочетание, для которого сумма весов рёбер паросочетания имеет максимальное значение. Если граф не является полным двудольным, отсутствующие рёбра добавляются с нулевым весом. Задача поиска такого паросочетания известна как задача о назначениях. Замечательный венгерский алгоритм решает задачу о назначениях и был одним из первых алгоритмов комбинаторной оптимизации. Задача может быть решена с помощью модифицированного поиска кратчайшего пути в алгоритме пополняющего пути. Если используется алгоритм Беллмана — Форда, время работы будет ${\displaystyle O(V^{2}E)}$, или цену ребра можно сдвинуть для достижения времени ${\displaystyle O(V^{2}\log {V}+VE)}$ при применении алгоритма Дейкстры с Фибоначчиевой кучей[12]. [13]

Имеется алгоритм полиномиального времени для нахождения наибольшего паросочетания или паросочетания максимального веса в графе, не являющемся двудольным. Следуя Джеку Эдмондсу его называют методом путей, деревьев и цветов или просто алгоритмом Эдмондса для паросочетаний. Алгоритм использует двунаправленные дуги. Обобщение той же техники может быть использовано для поиска максимального независимого множества в графах без клешней. Алгоритм Эдмодса был впоследствии улучшен до времени работы ${\displaystyle O({\sqrt {V}}E)}$, что соответствует алгоритмам для двудольных графов[14]. Другой (рандомизированный) алгоритм, разработанный Муча и Санковсим (Mucha, Sankowski)[10], основанный на быстром произведении матриц, даёт сложность ${\displaystyle O(V^{2.376})}$.

Максимальное паросочетание можно найти простым жадным алгоритмом. Cамым большим максимальным паросочетанием является наибольшее паросочетание, которое может быть найдено за полиномиальное время. Однако неизвестно никакого полиномиального по времени алгоритма для нахождения наименьшего максимального паросочетания, то есть максимального паросочетания, содержащего наименьшее возможное число рёбер.

Заметим, что наибольшее паросочетание из k рёбер является рёберным доминирующим множеством с k рёбрами. И обратно, если задано минимальное рёберное доминирующее множество с k рёбрами, мы можем построить наибольшее паросочетание с k рёбрами за полиномиальное время. Таким образом, задача нахождения минимального по размеру максимального паросочетания эквивалентна задаче нахождения минимального рёберного доминирующего множества[15]. Обе эти задачи оптимизации известны как NP-трудные, а их распознавательные версии являются классическими примерами NP-полных задач[16]. Обе задачи могут быть аппроксимированы с коэффициентом 2 с полиномиальным временм — просто находим произвольное максимальное паросочетание M[17].

Число паросочетаний в графе известно как индекс Хосойи. Вычисление этого числа является #P-полной задачей. Задача остаётся #P-полной в специальном случае перечисления совершенных паросочетаний в двудольном графе, поскольку вычисление перманента случайной 0-1 матрицы (другая #P-полная задача) — это то же самое, что вычисление числа совершенных паросочетаний в двудольном графе, имеющем заданную матрицу в качестве матрицы смежности. Существует, однако, рандомизированная аппроксимационная схема полиномиального времени для вычисления числа паросочетаний в двудольном графе[18]. Замечательная теорема Кастелейна, утверждающая, что число совершенных паросочетаний в планарном графе может быть вычислено в точности за полиномиальное время с помощью алгоритма FKT.

Число совершенных паросочетаний в полном графе K_n (с чётным n) задаётся двойным факториалом (n − 1)!![19]. Число паросочетаний в полном графе без ограничения, чтобы паросочетание было совершенным, задаётся телефонными номерами[20].

Одной из основных задач в теории паросочетаний является поиск всех рёбер, которые могут быть расширены до наибольшего паросочетания. Лучший детерминированный алгоритм решения этой задачи работает за время ${\displaystyle O(VE)}$[21]. Существует рандомизированный алгоритм, решающий задачу за время ${\displaystyle {\tilde {O}}(V^{2.376})}$[22]. В случае двудольного графа можно найти наибольшее паросочетание и использовать его для нахождения всех максимально-паросочетаемых рёбер за линейное время[23]; что даст в результате ${\displaystyle O(V^{1/2}E)}$ для общих двудольных графов и ${\displaystyle O((V/\log V)^{1/2}E)}$ для плотных двудольных графов с ${\displaystyle E=\Theta (V^{2})}$. В случае, если одно из наибольших паросочетаний известно заранее[24], общее время работы алгоритма будет ${\displaystyle O(V+E)}$.