Теорема Мендельсона — Далмейджа

Теорема Мендельсона — Далмейджа — утверждение о свойстве паросочетаний в двудольных графах: если для двудольного графа $G=(X,Y,E)$ с подмножествами вершин $X_{1}\subseteq X$ и $Y_{2}\subseteq Y$ существуют паросочетания $M_{1}$ и $M_{2}$ такие, что $M_{1}$ насыщает $X_{1}$, а $M_{2}$ насыщает $Y_{2}$, то существует паросочетание $M$, которое насыщает одновременно множества $X_{1}$ и $Y_{2}$ (паросочетание $M$ насыщает подмножество вершин, если для любой вершины в этом подмножестве существует ребро из $M$, которое инцидентно этой вершине).

Паросочетания $M_{1}$ (красное), $M_{2}$ (зелёное) и $M$ (синее) из утверждения теоремы. Паросочетание $M_{1}$ насыщает множество $X_{1}=\{x_{1},x_{2},x_{3},x_{5},x_{6}\}$ (вершины на рисунке пронумерованы сверху вниз). Паросочетание $M_{2}$ насыщает множество $Y_{2}=\{y_{1},y_{2},y_{3},y_{4},y_{5}\}$. Паросочетание $M$ насыщает оба этих множества.

Доказана Натаном Мендельсоном и Ллойдом Далмейджем в 1958 году. Следствие из теоремы даёт один из алгоритмов построения оптимальной рёберной раскраски двудольного графа (или, что то же самое, разбиения множества рёбер двудольного графа на наименьшее число паросочетаний).

Следствия

В двудольном графе существует паросочетание, насыщающее все вершины максимальной степени. Действительно, если максимальная степень вершины в двудольном графе равняется $\Delta$, то можно взять в качестве множества $X_{1}$ все вершины левой доли со степенью $\Delta$, а в качестве множества $Y_{2}$ — все вершины правой доли со степенью $\Delta$ (одно из множеств $X_{1}$ и $Y_{2}$ может быть и пустым); из теоремы Холла следует, что существуют паросочетания $M_{1}$ и $M_{2}$, насыщающие множества $X_{1}$ и $Y_{2}$ соответственно. Значит, по теореме Мендельсона — Далмейджа, существует и паросочетание $M$, насыщающее все вершины степени $\Delta$.

Множество рёбер двудольного графа с максимальной степенью вершины $\Delta$ можно разбить на $\Delta$ паросочетаний, или, иными словами, для рёберной раскраски этого графа необходимо и достаточно $\Delta$ цветов (этот результат впервые получен Кёнигом). Поскольку в графе существует паросочетание, насыщающее все вершины степени $\Delta$, то удаление из графа всех рёбер этого паросочетания даёт граф с максимальной степенью вершин $\Delta -1$; эту процедуру можно повторить до тех пор, пока в графе не останется рёбер.

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

Доказательство теоремы Мендельсона — Далмейджа и следствий из неё фактически является алгоритмом разбиения рёбер двудольного графа на наименьшее число паросочетаний.

Алгоритм выполняет $\Delta$ шагов, на каждом нужно построить паросочетания $M_{1}$ и $M_{2}$ (это можно сделать алгоритмом Хопкрофта — Карпа за время $O(|E|{\sqrt {|V|}})$) и паросочетание $M$ (это можно сделать за время $O(|E|)$). Итоговая сложность работы алгоритма — $O(\Delta |E|{\sqrt {|V|}})$.

Ссылки

• Mendelsohn, N. S., Dulmage, A. L. Some Generalizations of the Problem of Distinct Representatives // Canadian Journal of Mathematics. — 1958. — Vol. 10. — P. 230—241.
• Свами М., Тхуласираман К. Графы, сети и алгоритмы. — М.: Мир, 1984. — 455 с. — ISBN 978-5-458-33391-7.
• Kőnig, D. Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre // Mathematische Annalen. — 1916. — Т. 77, вып. 4. — С. 453—465. — doi:10.1007/BF01456961.