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

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

Определение[ | код]

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

Связанные определения[ | код]

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

Maximal-matching.svg

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

Maximum-matching-labels.svg

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

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

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

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

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

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

Свойства[ | код]

  • В любом графе без изолированных вершин число паросочетания и число рёберного покрытия в сумме дают число вершин[8].
    • В частности, если существует совершенное паросочетание, то оба числа равны |V| / 2.
  • Если A и B — два максимальных паросочетания, то |A| ≤ 2|B| и |B| ≤ 2|A|. Чтобы это увидеть, заметьте, что каждое ребро из B \ A может быть сопряжено максимум двум рёбрам из A \ B поскольку A — паросочетание. Однако каждое ребро A \ B сопряжено с ребром B \ A ввиду того, что B — максимальное. Следовательно,
Далее мы имеем
  • В частности, отсюда вытекает, что любое максимальное паросочетание является 2-аппроксимацией наибольшего паросочетания, а также 2-аппроксимацией минимального максимального паросочетания. Это неравенство точное. Например, если G — путь с тремя рёбрами и 4 вершинами, минимальный размер максимального паросочетания равен 1, а размер наибольшего паросочетания равен 2.

Многочлен паросочетаний[ | код]

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

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

,

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

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

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

Задачи нахождения паросочетания часто возникают при работе с двудольными графами. Поиск наибольшего паросочетания в двудольном графе[9] является, пожалуй, простейшей задачей. Алгоритм пополняющего пути получает его, находя пополняющий путь из каждой вершины в и добавляя его в паросочетание, если путь будет найден. Поскольку пополняющий путь может быть найден за время , время работы алгоритма будет . Это решение эквивалентно добавлению суперисточника с рёбрами ко всем вершинам , и суперстока с рёбрами из всех вершин , и поиску максимального потока из в . Все рёбра, по которым идёт поток из в , образуют максимальное паросочетание. Несколько быстрее работает алгоритм Хопкрофта — Карпа, работающий за время . Другой подход базируется на алгоритме быстрого умножения матриц и даёт сложность [10], что в теории лучше для достаточно плотных графов, но на практике алгоритм медленнее.[11]

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

Во взвешенном двудольном графе каждому ребру приписывается вес. Паросочетание максимального веса в двудольном графе[9] определяется как паросочетание, для которого сумма весов рёбер паросочетания имеет максимальное значение. Если граф не является полным двудольным, отсутствующие рёбра добавляются с нулевым весом. Задача поиска такого паросочетания известна как задача о назначениях. Замечательный венгерский алгоритм решает задачу о назначениях и был одним из первых алгоритмов комбинаторной оптимизации. Задача может быть решена с помощью модифицированного поиска кратчайшего пути в алгоритме пополняющего пути. Если используется алгоритм Беллмана — Форда, время работы будет , или цену ребра можно сдвинуть для достижения времени при применении алгоритма Дейкстры с Фибоначчиевой кучей[12]. [13]

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

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

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

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

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

Задачи перечисления[ | код]

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

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

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

Одной из основных задач в теории паросочетаний является поиск всех рёбер, которые могут быть расширены до наибольшего паросочетания. Лучший детерминированный алгоритм решения этой задачи работает за время [21]. Существует рандомизированный алгоритм, решающий задачу за время [22]. В случае двудольного графа можно найти наибольшее паросочетание и использовать его для нахождения всех максимально-паросочетаемых рёбер за линейное время[23]; что даст в результате для общих двудольных графов и для плотных двудольных графов с . В случае, если одно из наибольших паросочетаний известно заранее[24], общее время работы алгоритма будет .

Характеристики и замечания[ | код]

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

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

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

Приложения[ | код]

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

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

См. также[ | код]

Примечания[ | код]

  1. 1 2 Станислав Окулов. Дискретная математика. Теория и практика решения задач по информатике. Учебное пособие. — Litres, 2014-02-07. — С. 186. — 428 с. — ISBN 9785457534674.
  2. Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.
  3. Евстигнеев В.А.,Касьянов В.Н. Series-parallel poset // Словарь по графам в информатике / Под редакцией проф. Виктора Николаевича Касьянова. — Новосибирск: ООО «Сибирское Научное Издательство», 2009. — Т. 17. — (Конструирование и оптимизация программ). — ISBN 978-591124-036-3.
  4. Фуад Алескеров, Элла Хабина, Дмитрий Шварц. Бинарные отношения, графы и коллективные решения. — Litres, 2016-01-28. — С. 22. — 343 с. — ISBN 9785457966925.
  5. Рубчинский А. А. Дискретные математические модели. Начальные понятия и стандартные задачи. — Directmedia, 2014-08-06. — С. 136. — 269 с. — ISBN 9785445838029.
  6. Леонид Гладков, Владимир Курейчик, Виктор Курейчик. Генетические алгоритмы. — Litres, 2016-01-28. — С. 276. — 367 с. — ISBN 9785457965997.
  7. Леонид Гладков, Владимир Курейчик, Виктор Курейчик, Павел Сороколетов. Биоинспирированные методы в оптимизации. — Litres, 2016-01-28. — С. 330. — 381 с. — ISBN 9785457967472.
  8. Tibor Gallai. Über extreme Punkt- und Kantenmengen // Ann. Univ. Sci. Budapest. Eötvös Sect. Math.. — 1959. — Т. 2. — С. 133–138.
  9. 1 2 Douglas Brent West. Introduction to Graph Theory. — 2nd. — Prentice Hall, 1999. — ISBN 0-13-014400-2.
  10. 1 2 M. Mucha, P. Sankowski. Maximum Matchings via Gaussian Elimination // Proc. 45th IEEE Symp. Foundations of Computer Science. — 2004. — С. 248–255.
  11. Bala G. Chandran, Dorit S. Hochbaum. Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm. — 2011. — arXiv:1105.1569..
  12. M. Fredman, R. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms // Journal of the ACM. — 1987. — Т. 34, вып. 3. — С. 596–615.
  13. 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
  14. Silvio Micali, Vijay Vazirani. An 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.
  15. Yannakakis Mihalis, Gavril Fanica. Edge dominating sets in graphs // SIAM Journal on Applied Mathematics. — 1980. — Т. 38, вып. 3. — С. 364–372. — DOI:10.1137/0138030.
  16. 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.
  17. 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.
  18. 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. — Т. 37, вып. 5. — С. 1429–1454. — DOI:10.1137/050644033.
  19. David Callan. A combinatorial survey of identities for the double factorial. — 2009. — arXiv:0906.1317.
  20. Extremal problems for topological indices in combinatorial chemistry // Journal of Computational Biology. — 2005. — Т. 12, вып. 7. — С. 1004–1013. — DOI:10.1089/cmb.2005.12.1004.
  21. Marcelo H.de Carvalho, Joseph Cheriyan. An algorithm for ear decompositions of matching-covered graphs // Proc. ACM/SIAM Symposium on Discrete Algorithms (SODA). — 2005. — С. 415–423.
  22. Michael O. Rabin, Vijay V. Vazirani. Maximum matchings in general graphs through randomization // J. of Algorithms. — 1989. — Т. 10. — С. 557–567.
  23. 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.
  24. Aris Gionis, Arnon Mazza, Tamir Tassa. k-Anonymization revisited // International Conference on Data Engineering (ICDE). — 2008. — С. 744–753.
  25. Смотрите, например, Nenad Trinajstić, Douglas J. Klein, Milan Randić. On some solved and unsolved problems of chemical graph theory. — 1986. — Т. 30, вып. S20. — С. 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.

Ссылки[ | код]