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

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

Определение

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

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

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

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

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

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

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

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

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

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

Свойства

Число совершенных паросочетаний в двудольном графе равно перманенту его матрицы смежности.
В любом графе без изолированных вершин число паросочетания и число рёберного покрытия в сумме дают число вершин^[8].
- В частности, если существует совершенное паросочетание, то оба числа равны |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 — число вершин в графе. Оба определения имеют свои области применения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

См. также

Примечания

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

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

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

S. J. Cyvin, Ivan Gutman. Kekule Structures in Benzenoid Hydrocarbons. — Springer-Verlag, 1988.
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

[:0-1] ¹ ² Станислав Окулов. Дискретная математика. Теория и практика решения задач по информатике. Учебное пособие. — Litres, 2014-02-07. — С. 186. — 428 с. — ISBN 9785457534674.

[2] Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985, Chapter 5.

[GrapDict-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.

[Wes01-9] ¹ ² Douglas Brent West. Introduction to Graph Theory. — 2nd. — Prentice Hall, 1999. — ISBN 0-13-014400-2.

[Mucha-10] ¹ ² 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..

[Fredman87-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 $\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.

[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 Архивная копия от 5 сентября 2013 на Wayback Machine и Minimum Maximal Matching Архивная копия от 6 марта 2014 на Wayback Machine в web compendium Архивная копия от 2 октября 2013 на Wayback Machine.

[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 $O(VE)$ 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]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]