Теорема Татта о существовании полного паросочетания

Определение:

$\mathrm{odd}({G})$ — число нечетных компонент связности в графе ${G}$, где нечетная компонента (англ. odd component) — это компонента связности, содержащая нечетное число вершин.

Определение:

Множество Татта графа ${G}$ — множество $S \subset {V_{G}}$, для которого выполнено условие: $\mathrm{odd}({G} \setminus S) \gt \left\vert S \right\vert$

Критерий Татта

Пусть ${G'}$ — граф, полученный из ${G}=\langle {V},{E} \rangle$ добавлением ребер, при этом в ${G'}$ нет полного паросочетания, но оно появляется при добавлении любого нового ребра.

Так как новых вершин не добавлялось, то ${G'}=\langle {V},{E'}\rangle$

Пусть $U = \{ v \in {V}: \deg_{G'} (v) = n - 1 \}$.

Очевидно, что $\left\vert U \right\vert \ne n$, потому что ${G'}$ — не полный граф.

Лемма:

${G'} \setminus U$ — объединение несвязных полных графов.

Доказательство:

$\triangleright$

Пусть это не так, тогда существуют вершины $x,y,z \in {V} \setminus U$, такие что $xy, yz \in {E'}$, но $xz \notin {E'}$. Так как $y \notin U$, то $\exists t \notin U: yt \notin {E'}$. По построению ${G'}$ в графе ${G'}+xz$ существует полное паросочетание $M_1$. Аналогично, в графе ${G'}+yt$ существует полное паросочетание $M_2$. Так как в ${G'}$ нет полного паросочетания, то $xz \in M_1$ и $yt \in M_2$. Возможны два случая: Вершины $x,z$ и $y,t$ лежат в разных полных подграфах графа ${G'} \setminus U$, обозначим их $H_1$ и $H_2$, соответственно. Покроем вершины подграфа $H_1$ паросочетанием $M_2$, при этом заметим, что ребро $xz$ не входит в это паросочетание. Аналогично покроем паросочетанием $M_1$ вершины подрафа $H_2$ и ребро $yt$ не войдет в это паросочетание. Если остались непокрытые вершины, то покроем их ребрами из любого паросочетания $M_1$ или $M_2$. Таким образом, мы получим полное паросочетание в графе ${G'}$, что противоречит его построению. К доказательству 2-ого пункта леммы. Вершины $x,y,z$ и $t$ лежат в одном подграфе графа ${G'} \setminus U$. Построим граф $H$, такой что ${V_{H}}={V}$ и ${E_{H}}=M_1 \oplus M_2$. Получим, что вершины $x,y,z$ и $t$ лежат на каком-то чередующемся цикле из ребер $M_1$ и $M_2$. Рассмотрим подробнее, почему это будет именно так. Ребро $xz$ принадлежит паросочетанию $M_1$, значит вершина $y$ и какая-то произвольная вершина $v$ будут покрыты ребром паросочетания $M_1$, при этом эти ребра не принадлежат паросочетанию $M_2$, но ребра $yt$ и $vu$, где $u$ — произвольная вершина, принадлежат $M_2$ и не принадлежат $M_1$ и так далее. Таким образом и получается чередующийся цикл в графе $H$. В силу симметричности $x$ и $z$ можно считать, что вершины расположены в порядке $tzxy$. Тогда существует путь $P_1=t..zx..y$ и полное паросочетание в нем, следовательно существует и путь $P_2=t..zy..x$, содержащий только ребра графа ${G'}$. Тогда на пути $x..y$ возьмем ребра из паросочетания $M_2$, а на пути $t..z$ - ребра из паросочетания $M_1$. Непокрытыми остались вершины $z$ и $y$, которые мы покроем ребром $yz$. Вершины, не принадлежащие рассматриваемому циклу, покроем ребрами любого из паросочетаний $M_1, M_2$ (выберем ребра одного из них). Таким образом, получили полное паросочетание в графе ${G'}$, противоречие. В каждом из возможных случаев получили противоречие, значит, наше начальное предположение тоже неверно и ${G'} \setminus U$ — объединение несвязных полных графов, лемма доказана.

$\triangleleft$

Теорема Татта

Теорема:

В графе ${G}$ существует полное паросочетание $\Leftrightarrow$ $\forall S \subset {V}$ выполнено условие: $\mathrm{odd}({G} \setminus S) \leqslant \left\vert S \right\vert$ (то есть в графе ${G}$ нет ни одного множества Татта)

Доказательство:

$\triangleright$

$\Rightarrow$ Рассмотрим $M$ — полное паросочетание в графе ${G}$ и множество вершин $S \subset {V}$. Одна из вершин каждой нечетной компоненты связности графа ${G} \setminus S$ соединена ребром паросочетания $M$ с какой-то вершиной из $S$. Иначе мы не сможем покрыть паросочетанием все вершины этой компоненты связности и получим противоречие с тем, что полное паросочетание существует по условию теоремы. Таким образом, получаем, что $\mathrm{odd}({G} \setminus S) \leqslant \left\vert S \right\vert$. $\Leftarrow$ Пусть для графа ${G}$ выполнено, что $\mathrm{odd}({G} \setminus S) \leqslant \left\vert S \right\vert$, но полного паросочетания в этом графе не существует. Рассмотрим граф ${G'}$ и множество вершин $U$ (из леммы). Так как число нечетных компонент не увеличивается при добавлении новых ребер, то $\forall S \subset {V}$ выполнено $\mathrm{odd}({G'} \setminus S) \leqslant \mathrm{odd}({G} \setminus S) \leqslant \left\vert S \right\vert$. По лемме, доказанной выше: ${G'} \setminus U$ — объединение несвязных полных графов. Очевидно, что в каждой четной компоненте связности графа ${G'} \setminus U$ мы можем построить полное паросочетание. В каждой нечетной компоненте этого графа построим паросочетание, которое покрывает все вершины кроме одной, оставшуюся непокрытой вершину, соединим с какой-то вершиной множества $U$. При этом мы будем использовать различные вершины из $U$, это возможно, так как $\mathrm{odd}({G'} \setminus U) \leqslant \left\vert U \right\vert$. Если все вершины множества $U$ оказались покрытыми, то мы получили полное паросочетание в графе ${G'}$. Противоречие, так как по построению в ${G'}$ нет полного паросочетания. Значит, в $U$ осталось какое-то количество непокрытых вершин, при этом их четное число, потому что число вершин в ${G'}$ четно, так как $\mathrm{odd}({G'} \setminus \varnothing) \leqslant \left\vert \varnothing \right\vert = 0$ и уже покрыто паросочетанием четное число вершин. Так как в множество $U$ входят вершины, которые в ${G'}$ смежны со всеми остальными, то мы сможем разбить оставшиеся вершины на пары и покрыть их паросочетанием. Таким образом, получили в ${G'}$ полное паросочетание, что противоречит тому, как мы задали этот граф изначально. Значит, начальное предположение не верно, и в ${G}$ существует полное паросочетание.

$\triangleleft$

См. также

• Матрица Татта и связь с размером максимального паросочетания в двудольном графе
• Паросочетания: основные определения, теорема о максимальном паросочетании и дополняющих цепях
• Декомпозиция Эдмондса-Галлаи

Источники информации

• Д.В Карпов. Теория графов (2 глава, стр. 29)
• Wikipedia — Tutte theorem