Русская Википедия:Паросочетание

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

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

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

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

Файл:Maximal-matching.svg

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

Файл:Maximum-matching-labels.svg

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

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

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

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

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

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

Свойства

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

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

  <math>|A \setminus B| \le 2|B \setminus A|</math>

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

<math>|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|</math>

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

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

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

<math>\sum_{k\geq0} m_k x^k</math>

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

<math>\sum_{k\geq0} (-1)^k m_k x^{n-2k}</math>,

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

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

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

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

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

Пополняющий путь - это путь вида <math>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</math>, для которого истинно <math>\{v_{i-1}, v_i\} \in M \Leftrightarrow \{v_i, v_{i+1}\} \notin M </math> при <math>0 \leqslant i \leqslant l</math>. Пополняющий путь называется расширяющим, если <math>v_0, v_l \notin M </math>.

Лемма: Для любого графа <math>G = (V, E) </math>, паросочетания <math>M </math> и пополняющего пути <math>P </math> справедливо <math>M \oplus E(P) </math> паросочетание и <math>|M \oplus E(P)| = |M|+ 1 </math>. Доказательство: Пусть <math>G' = (V, M) </math>, <math>G = (V, M \oplus E(P)) </math> и <math>v </math> - начальная вершина <math>P </math>, так что <math>\delta_{G'}(v) = 0 </math> и <math>\delta_{G}(v) = 1

</math>, а также <math>w </math> - последняя вершина <math>P </math>, так что <math>\delta_{G'}(w) = 0 </math> и <math>\delta_{G}(w) = 1 </math>, и <math>u </math> - промежуточная вершина <math>P </math>, так что <math>\delta_{G'}(u) = \delta_{G}(u) = 1 </math>. Из этого следует, что в граф будет добавлено на одно ребро больше, чем удалено из него.

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

• <math>G_i </math> является изолированной вершиной или
• <math>G_i </math> является циклом четной длины или
• <math>G_i </math> является путем четной длины или
• <math>G_i </math> является путем нечетной длины

Вершины в <math>G_i

</math> происходят попеременно из <math>M </math> и <math>N </math>. Пусть <math>d(G_i) = |E_i \cap N| - |E_i \cap M| \subset \{-1, 0, 1\} </math>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

См. также

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

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

1. Шаблон:Книга
2. Шаблон:Книга

1. Шаблон:Книга
2. Шаблон:Книга

Ссылки

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

Шаблон:Rq