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

Теорема Мендельсона — Далмейджа — утверждение о свойстве паросочетаний в двудольных графах: если для двудольного графа $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$ насыщает оба этих множества.

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

Следствия

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

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

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

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

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

Ссылки

• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья