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

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

ОпределениеПравить

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

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

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

 

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

 

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

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

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

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

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

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

СвойстваПравить

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

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

  $|A\setminus <!--\; \setminus \; -->B|\le <!--\; \le \; -->2|B\setminus <!--\; \setminus \; -->A|$$|A\setminus B|\leq 2|B\setminus A|$ 

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

$|A|=|A\cap <!--\; \cap \; -->B|+|A\setminus <!--\; \setminus \; -->B|\le <!--\; \le \; -->2|B\cap <!--\; \cap \; -->A|+2|B\setminus <!--\; \setminus \; -->A|=2|B|$$|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 будет

$\underset{k\ge <!--\; \ge \; -->0}{\sum <!--\; \sum \; -->}{m}_k{x}^k$$\sum _{{k\geq 0}}m_{k}x^{k}$ 

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

$\underset{k\ge <!--\; \ge \; -->0}{\sum <!--\; \sum \; -->}(-<!--\; -\; -->1{)}^k{m}_k{x}^{n-<!--\; -\; -->2k}$$\sum _{{k\geq 0}}(-1)^{k}m_{k}x^{{n-2k}}$ ,

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

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

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

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

1. Установи $M=\mathrm{\varnothing <!--\; \varnothing \; -->}$$M=\emptyset$ .
2. Пока имеются расширяющие пополняющие пути $P$$P$ :
   1. $M=M\oplus <!--\; \oplus \; -->E(P)$$M=M\oplus E(P)$ 

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Алгоритм Эдмондса для паросочетаний

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

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

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

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

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

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

Задачи перечисленияПравить

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

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

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

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

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

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

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

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

ПриложенияПравить

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

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

См. такжеПравить

• Рёберная раскраска
• Независимое множество
• Декомпозиция Далмейджа-Мендельсона
• Устойчивое паросочетание
• Оптимальное паросочетание^[en]
• Кососимметический граф^[en]
• Словарь терминов теории графов

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

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.

СсылкиПравить

• Пример решения задачи на 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