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

Определение

Пусть дан граф G = ( V , E ), паросочетание M в G — это множество попарно несмежных рёбер, то есть рёбер, не имеющих общих вершин, т.е. ${\displaystyle \forall e,f\in M:e\cap f=\emptyset }$ .

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

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

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

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

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

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

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

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

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

Свойства

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

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

  ${\displaystyle |A\setminus B|\leq 2|B\setminus A|}$

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

${\displaystyle |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 будет

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

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

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

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

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

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

Задачи нахождения паросочетания часто возникают при работе с двудольными графами . Поиск наибольшего паросочетания в двудольном графе ${\displaystyle G=(V=(X,Y),E)}$ является, пожалуй, простейшей задачей. Алгоритм пополняющего пути получает его, находя пополняющий путь из каждой вершины ${\displaystyle x\in X}$ в ${\displaystyle Y}$ и добавляя его в паросочетание, если путь будет найден. Альтернативный способ решения заключается в том, что паросочетание будет дополняться до тех пор, пока существуют расширяющие дополняющие пути:

1. Установи ${\displaystyle M=\emptyset }$ .
2. Пока имеются расширяющие пополняющие пути ${\displaystyle P}$ :
   1. ${\displaystyle M=M\oplus E(P)}$ , где ${\displaystyle \oplus }$ - симметрическая разность множеств.

Пополняющий путь - это путь вида ${\displaystyle v_{0},\{v_{0},v_{1}\},v_{1},\{v_{1},v_{2}\},v_{2},\dots ,v_{l-1},\{v_{l-1},v_{l}\},v_{l}}$ , для которого истинно ${\displaystyle \{v_{i-1},v_{i}\}\in M\Leftrightarrow \{v_{i},v_{i+1}\}\notin M}$ при ${\displaystyle 0\leqslant i\leqslant l}$ . Пополняющий путь называется расширяющим, если ${\displaystyle v_{0},v_{l}\notin M}$ .

Лемма: Для любого графа ${\displaystyle G=(V,E)}$ , паросочетания ${\displaystyle M}$ и пополняющего пути ${\displaystyle P}$ справедливо ${\displaystyle M\oplus E(P)}$ паросочетание и ${\displaystyle |M\oplus E(P)|=|M|+1}$ . Доказательство: Пусть ${\displaystyle G'=(V,M)}$ , ${\displaystyle G''=(V,M\oplus E(P))}$ и ${\displaystyle v}$ - начальная вершина ${\displaystyle P}$ , так что ${\displaystyle \delta _{G'}(v)=0}$ и ${\displaystyle \delta _{G''}(v)=1}$ , а также ${\displaystyle w}$ - последняя вершина ${\displaystyle P}$ , так что ${\displaystyle \delta _{G'}(w)=0}$ и ${\displaystyle \delta _{G''}(w)=1}$ , и ${\displaystyle u}$ - промежуточная вершина ${\displaystyle P}$ , так что ${\displaystyle \delta _{G'}(u)=\delta _{G''}(u)=1}$ . Из этого следует, что в граф будет добавлено на одно ребро больше, чем удалено из него.

Лемма: Для любого графа ${\displaystyle G=(V,E)}$ и паросочетаний ${\displaystyle M}$ , ${\displaystyle N}$ таких, что ${\displaystyle |M|<|N|}$ справедливо следующее: граф ${\displaystyle H=(V,M\oplus N)}$ содержит минимум ${\displaystyle |N|-|M|}$ не пересекающихся в вершинах пополняющих путей относительно ${\displaystyle M}$ в ${\displaystyle G}$ . Доказательство: Пусть ${\displaystyle G_{M}=(V,M)}$ и ${\displaystyle G_{N}=(V,N)}$ , при этом действительно ${\displaystyle \delta (G_{M})\subset \{0,1\}}$ и ${\displaystyle \delta (G_{N})\subset \{0,1\}}$ и таким образом следует ${\displaystyle \delta (H)\subset \{0,1,2\}}$ . Пусть ${\displaystyle G_{i}=(V,E_{i})}$ при ${\displaystyle 1\leqslant i\leqslant g}$ компоненты связности графа ${\displaystyle H}$ . Из ${\displaystyle \delta (H)\subset \{0,1,2\}}$ следует

• ${\displaystyle G_{i}}$ является изолированной вершиной или
• ${\displaystyle G_{i}}$ является циклом четной длины или
• ${\displaystyle G_{i}}$ является путем четной длины или
• ${\displaystyle G_{i}}$ является путем нечетной длины

Вершины в ${\displaystyle G_{i}}$ происходят попеременно из ${\displaystyle M}$ и ${\displaystyle N}$ . Пусть ${\displaystyle d(G_{i})=|E_{i}\cap N|-|E_{i}\cap M|\subset \{-1,0,1\}}$

, а ${\displaystyle d(G_{i})=1}$ только если ${\displaystyle G_{i}}$ - пополняющий путь. ${\displaystyle \sum _{i=1}^{g}d(G_{i})=|N\setminus M|-|M\setminus N|=|N|-|M|}$ и это означает, что должно существовать минимум ${\displaystyle |N|-|M|}$ компонент ${\displaystyle G_{i}}$ с ${\displaystyle d(G_{i})=1}$ и, как следствие, дополняющих путей. Согласно определению компонент связности, такие дополняющи пути не будут пересекаться в вершинах.

Найти дополняющий путь можно следующим образом:

1. Даны ${\displaystyle G=(V,W,E)}$ двудольный граф и паросочетание ${\displaystyle M}$ .
2. Создай ${\displaystyle G'=(V\cup W,E'\cup E'')}$ , где
   1. ${\displaystyle E'=\{(v,w)\mid \{v,w\}\in E\setminus M\land v\in V\land w\in W\}}$
   2. ${\displaystyle E''=\{(w,v)\mid \{v,w\}\in M\land v\in V\land w\in W\}}$
3. Поиск дополняющего пути сводится к поиску в ${\displaystyle G'}$ из свободной вершины ${\displaystyle v\in V}$ в свободную вершину ${\displaystyle w\in W}$ .

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

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

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

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

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

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

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

1. Дан граф ${\displaystyle G=(V,E)}$ .
2. Установи ${\displaystyle M=\emptyset }$ .
3. Пока множество ${\displaystyle E}$ не пустое:
   1. Выбери ${\displaystyle e\in E}$ .
   2. Установи ${\displaystyle M=M\cup \{e\}}$ .
   3. Установи ${\displaystyle E=\{e'\in E\mid e'\cap e=\emptyset \}}$ .
4. Выведи ${\displaystyle M}$ .

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

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

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

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

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

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

Одной из основных задач в теории паросочетаний является поиск всех рёбер, которые могут быть расширены до наибольшего паросочетания. Лучший детерминированный алгоритм решения этой задачи работает за время ${\displaystyle O(VE)}$ . Существует рандомизированный алгоритм, решающий задачу за время ${\displaystyle {\tilde {O}}(V^{2.376})}$ . В случае двудольного графа можно найти наибольшее паросочетание и использовать его для нахождения всех максимально паросочетаемых рёбер за линейное время ; что даст в результате ${\displaystyle O(V^{1/2}E)}$ для общих двудольных графов и ${\displaystyle O((V/\log V)^{1/2}E)}$ для плотных двудольных графов с ${\displaystyle E=\Theta (V^{2})}$ . В случае, если одно из наибольших паросочетаний известно заранее , общее время работы алгоритма будет ${\displaystyle 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. . — Oxford University Press, 1998. — ISBN 978-0-19-850162-6 .

Ссылки

• от 22 марта 2016 на Wayback Machine
• от 7 января 2012 на Wayback Machine
• от 25 октября 2005 на Wayback Machine