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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

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

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

Maximal-matching.svg

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

Maximum-matching-labels.svg

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

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

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

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

Можно доказать, что паросочетание является максимальным в том и только в том случае, если не существует пополняющего пути. (Этот результат иногда называют леммой Берга[en].)

Свойства[править | править вики-текст]

В любом графе без изолированных вершин число паросочетания и число рёберного покрытия[en] в сумме дают число вершин[3]. Если существует совершенное паросочетание, то оба числа равны |V| / 2.

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

|A \setminus B| \le 2|B \setminus A|

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

|A| = |A \cap B| + |A \setminus B| \le 2|B \cap A| + 2|B \setminus A| = 2|B|

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

Полиномы паросочетаний[править | править вики-текст]

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

\sum_{k\geq0} m_k x^k

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

\sum_{k\geq0} (-1)^k m_k x^{n-2k}

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

Алгоритмы и вычислительная сложность[править | править вики-текст]

Максимальное паросочетание в двудольном графе[править | править вики-текст]

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

Во взвешенном двудольном графе[править | править вики-текст]

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

Максимальные паросочетания[править | править вики-текст]

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

Наибольшие паросочетания[править | править вики-текст]

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

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

Задачи перечисления[править | править вики-текст]

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

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

Нахождение всех рёбер, паросочетаемых рёбер[править | править вики-текст]

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

Характеристики и замечания[править | править вики-текст]

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

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

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

Приложения[править | править вики-текст]

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.
  2. Евстигнеев В.А.,Касьянов В.Н. Series-parallel poset // Словарь по графам в информатике / Под редакцией проф. Виктора Николаевича Касьянова. — Новосибирск: ООО «Сибирское Научное Издательство», 2009. — Т. 17. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3.
  3. Tibor Gallai Über extreme Punkt- und Kantenmengen // Ann. Univ. Sci. Budapest. Eötvös Sect. Math.. — 1959. — Т. 2. — С. 133–138.
  4. 1 2 Douglas Brent West Introduction to Graph Theory. — 2nd. — Prentice Hall, 1999. — ISBN 0-13-014400-2.
  5. 1 2 M. Mucha, P. Sankowski Maximum Matchings via Gaussian Elimination // Proc. 45th IEEE Symp. Foundations of Computer Science. — 2004. — С. 248–255.
  6. Bala G. Chandran, Dorit S. Hochbaum Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm. — 2011. — arΧiv1105.1569.
  7. M. Fredman, R. Tarjan Fibonacci heaps and their uses in improved network optimization algorithms // Journal of the ACM. — 1987. — В. 3. — Т. 34. — С. 596–615.
  8. Rainer Burkard, Mauro Dell’Amico, Silvano Martello Assignment Problems. — Philadelphia: SIAM, Society for Industrial and Applied Mathematics, 2009. — С. 77-79, 98. глава 4.1.3 Historical notes, books, and surveys, глава 4.4.3 Efficient implementations
  9. Silvio Micali, Vijay Vazirani An \scriptstyle O(\sqrt{|V|}\cdot|E|) algorithm for finding maximum matching in general graphs // Proc. 21st IEEE Symp. Foundations of Computer Science. — 1980. — С. 17–27. — DOI:10.1109/SFCS.1980.12
  10. Yannakakis Mihalis, Gavril Fanica Edge dominating sets in graphs // SIAM Journal on Applied Mathematics. — 1980. — В. 3. — Т. 38. — С. 364–372. — DOI:10.1137/0138030
  11. Michael R. Garey, David S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness. — W.H. Freeman, 1979. — ISBN 0-7167-1045-5.. Рёберное доминирующее множество обсуждается при рассмотрении задач нахождения доминирующих множеств, задачи GT2 в приложении A1.1. Минимальное по размеру наибольшее паросочетание — это задача GT10 в приложении A1.1.
  12. Giorgio Ausiello, Pierluigi Crescenzi, Giorgio Gambosi, Viggo Kann, Alberto Marchetti-Spaccamela, Marco Protasi Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. — Springer, 2003. Минимальное доминирующее рёберное множество — это задача GT3 в приложении B (страница 370). Минимальное по размеру максимальное паросочетание — это задача GT10 в приложении B (страница 374). Смотрите также Minimum Edge Dominating Set и Minimum Maximal Matching в web compendium.
  13. Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, Eric Vigoda Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems // SIAM Journal on Computing. — 2008. — В. 5. — Т. 37. — С. 1429–1454. — DOI:10.1137/050644033
  14. David Callan A combinatorial survey of identities for the double factorial. — 2009. — arΧiv0906.1317
  15. Extremal problems for topological indices in combinatorial chemistry // Journal of Computational Biology. — 2005. — В. 7. — Т. 12. — С. 1004–1013. — DOI:10.1089/cmb.2005.12.1004
  16. Marcelo H.de Carvalho, Joseph Cheriyan An O(VE) algorithm for ear decompositions of matching-covered graphs // Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA). — 2005. — С. 415–423.
  17. Michael O. Rabin, Vijay V. Vazirani Maximum matchings in general graphs through randomization // J. of Algorithms. — 1989. — Т. 10. — С. 557–567.
  18. Tamir Tassa Finding all maximally-matchable edges in a bipartite graph // Theoretical Computer Science. — 2012. — Т. 423. — С. 50–58. — DOI:10.1016/j.tcs.2011.12.071
  19. Aris Gionis, Arnon Mazza, Tamir Tassa k-Anonymization revisited // International Conference on Data Engineering (ICDE). — 2008. — С. 744–753.
  20. Смотрите, например, Nenad Trinajstić, Douglas J. Klein, Milan Randić On some solved and unsolved problems of chemical graph theory. — 1986. — В. S20. — Т. 30. — С. 699–742. — DOI:10.1002/qua.560300762

Литература для дальнейшего чтения[править | править вики-текст]

  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.

Ссылки[править | править вики-текст]