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

В теории графов паросочетание, или независимое множество рёбер в графе, — это набор попарно несмежных рёбер.

Определение

Пусть дан граф G = (V,E), паросочетание M в G — это множество попарно несмежных рёбер, то есть рёбер, не имеющих общих вершин.

Связанные определения

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

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

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

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

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

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

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

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

Свойства

• Число совершенных паросочетаний в двудольном графе равно перманенту его матрицы смежности.
• В любом графе без изолированных вершин число паросочетания и число рёберного покрытия в сумме дают число вершин.
  • В частности, если существует совершенное паросочетание, то оба числа равны |V| / 2.

• Если A и B — два максимальных паросочетания, то |A| ≤ 2|B| и |B| ≤ 2|A|. Чтобы это увидеть, заметьте, что каждое ребро из B \ A может быть сопряжено максимум двум рёбрам из A \ B поскольку A — паросочетание. Однако каждое ребро A \ B сопряжено с ребром B \ A ввиду того, что B — максимальное. Следовательно,

  $|A\setminus B|\leq 2|B\setminus A|$

Далее мы имеем

$|A|=|A\cap B|+|A\setminus B|\leq 2|B\cap A|+2|B\setminus A|=2|B|$

• В частности, отсюда вытекает, что любое максимальное паросочетание является 2-аппроксимацией наибольшего паросочетания, а также 2-аппроксимацией минимального максимального паросочетания. Это неравенство точное. Например, если G — путь с тремя рёбрами и 4 вершинами, минимальный размер максимального паросочетания равен 1, а размер наибольшего паросочетания равен 2.

Многочлен паросочетаний

Производящая функция числа k-рёберных паросочетаний в графе называется многочлен паросочетаний. Пусть G — граф и m_k — число k-рёберных паросочетаний. Полиномом паросочетаний графа G будет

$\sum _{k\geq 0}m_{k}x^{k}$

Есть другое определение полинома паросочетаний

$\sum _{k\geq 0}(-1)^{k}m_{k}x^{n-2k}$,

где n — число вершин в графе. Оба определения имеют свои области применения.

Алгоритмы и вычислительная сложность

Наибольшее паросочетание в двудольном графе

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

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

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

Наибольшие паросочетания

Основная статья: Алгоритм Эдмондса для паросочетаний

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

Максимальные паросочетания

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

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

Задачи перечисления

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

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

Нахождение всех рёбер, паросочетаемых рёбер

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

Характеристики и замечания

Теорема Кёнига утверждает, что в двудольных графах размер наибольшего паросочетания равно размеру наименьшего вершинного покрытия. Из этого следует, что для двудольных графов задачи нахождения наименьшего вершинного покрытия, наибольшего независимого множества, и максимальной вершинной биклики могут быть решены за полиномиальное время.

Теорема Холла (или теорема о свадьбах) обеспечивает характеризацию двудольных графов, имеющих совершенные паросочетания, а теорема Татта даёт характеризацию произвольных графов.

Совершенное паросочетание порождает остовный 1-регулярный подграф, то есть 1-фактор. В общем случае остовный k-регулярный подграф — это k-фактор.

Приложения

Структурная формула Кекуле ароматических соединений состоит из совершенных паросочетаний их углеродного скелета, показывая местоположение двойных связей в химической структуре. Эти структуры названы в честь Фридриха Августа Кекуле, который показал, что бензол (в терминах теории графов — это цикл из 6 вершин) может быть представлен в виде такой структуры.

Индекс Хосойи — это число непустых паросочетаний плюс единица. Он применяется в вычислительной и математической химии для исследования органических соединений.

См. также

• Рёберная раскраска
• Независимое множество
• Декомпозиция Далмейджа-Мендельсона
• Устойчивое паросочетание
• Оптимальное паросочетание
• Кососимметический граф
• Словарь терминов теории графов

Литература для дальнейшего чтения

1. László Lovász, Michael D. Plummer. Matching Theory. — North-Holland, 1986. — ISBN 0-444-87916-1.
2. Introduction to Algorithms. — second. — MIT Press and McGraw–Hill, 2001. — ISBN 0-262-53196-8.

1. S. J. Cyvin, Ivan Gutman. Kekule Structures in Benzenoid Hydrocarbons. — Springer-Verlag, 1988.
2. Marek Karpinski, Wojciech Rytter. Fast Parallel Algorithms for Graph Matching Problems. — Oxford University Press, 1998. — ISBN 978-0-19-850162-6.

Ссылки

• Пример решения задачи на YouTube Архивная копия от 22 марта 2016 на Wayback Machine
• Алгоритм поиска наибольшего паросочетания в двудольном графе Архивная копия от 7 января 2012 на Wayback Machine
• A graph library with Hopcroft-Karp and Push-Relabel-based maximum cardinality matching implementation Архивная копия от 25 октября 2005 на Wayback Machine