Все теоремы

В математической дисциплине теории графов теорема Тутте , названная в честь Уильяма Томаса Тутта , представляет собой характеристику конечных неориентированных графов с идеальными паросочетаниями . Это частный случай формулы Тутта-Бержа .

Интуиция

Цель состоит в том, чтобы охарактеризовать все графы, которые не имеют идеального соответствия. Начнем с наиболее очевидного случая графа без идеального паросочетания: графа с нечетным числом вершин. В таком графе при любом сопоставлении остается хотя бы одна несовпадающая вершина, поэтому он не может быть идеальным.

Несколько более общий случай — несвязный граф, в котором один или несколько компонентов имеют нечетное количество вершин (даже если общее количество вершин четное). Назовем такие компоненты нечетными компонентами . При любом сопоставлении каждая вершина может сопоставляться только с вершинами того же компонента. Следовательно, любое сопоставление оставляет хотя бы одну несовпадающую вершину в каждом нечетном компоненте, поэтому оно не может быть идеальным.

Далее рассмотрим граф G с вершиной u такой, что если мы удалим из G вершину u и прилегающие к ней ребра, оставшийся граф (обозначенный $G - u$ ) будет иметь две или более нечетные компоненты. Как и выше, любое совпадение оставляет в каждом нечетном компоненте по крайней мере одну вершину, не совпадающую с другими вершинами в том же компоненте. Такая вершина может быть сопоставлена только с u . Но поскольку существует две или более несовпадающие вершины, и только одна из них может быть сопоставлена с u , по крайней мере еще одна вершина остается несовпадающей, поэтому сопоставление не является идеальным.

Наконец, рассмотрим граф G с таким набором вершин $U$ , что если мы удалим из G вершины $U$ и все смежные с ними ребра, оставшийся граф (обозначенный $G - U$ ) будет иметь более $| У |$ странные компоненты. Как объяснялось выше, любое сопоставление оставляет по крайней мере одну несовпадающую вершину в каждом нечетном компоненте, и они могут быть сопоставлены только с вершинами $U$ недостаточно вершин $, но на U$ для всех этих несовпадающих вершин, поэтому сопоставление не является идеальным.

Мы пришли к необходимому условию: если G имеет совершенное паросочетание, то для каждого подмножества вершин $U$ в G граф $G - U$ имеет не более $| У |$ странные компоненты. Теорема Тутте утверждает, что это условие одновременно необходимо и достаточно для существования идеального паросочетания.

Теорема Тутти

Граф $G = (V, E)$ имеет идеальное паросочетание тогда и только тогда, когда каждого подмножества $U$ из $V$ подграф G $для - U$ имеет не более $| У |$ нечетные компоненты ( компоненты связности, имеющие нечетное число вершин ). ^[1]

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

Сначала пишем условие:

(*)\qquad \forall U\subseteq V,\quad odd(G-U)\leq |U|

где $odd(X)$ обозначает количество нечетных компонент подграфа, индуцированного $X$ .

Необходимость (∗): Это направление уже обсуждалось в разделе «Интуиция» ниже, но давайте подведем здесь итоги доказательства. Рассмотрим граф $G$ с идеальным паросочетанием. Пусть $U$ — произвольное подмножество $V$ . Удалить $Ю.$ Пусть $C$ произвольная нечетная компонента в $G - U.$ — Поскольку $G$ имеет идеальное паросочетание, хотя бы одна вершина в $C$ должна соответствовать вершине $U.$ из Следовательно, каждый нечетный компонент имеет хотя бы одну вершину, совпадающую с вершиной из $U$ . Поскольку каждая вершина в $U$ может находиться в этом отношении не более чем с одним компонентом связности (поскольку при идеальном паросочетании она сопоставляется не более одного раза), $нечетный (G - U) \leq | У |$ . ^[2]

Достаточность (∗): Пусть $G$ — произвольный граф без идеального паросочетания. Мы найдем так называемый нарушитель Тутте , то есть подмножество $S$ множества $V$ такое, что $| С | < нечетный (грамм - S)$ . Мы можем предположить, что $G$ является максимальным по ребру, т. е. $G + e$ имеет идеальное паросочетание для каждого ребра $e,$ нет в $G.$ которого еще Действительно, если мы находим нарушителя Тутта $S$ в реберно-максимальном графе $G$ , то $S$ также является нарушителем Тутте в каждом охватывающем подграфе $G$ , поскольку каждый нечетный компонент $G - S$ будет разбит на, возможно, большее количество компонентов, по крайней мере один из которых снова будет странно.

Мы определяем $S$ как множество вершин степени $| В | - 1$ . Сначала мы рассмотрим случай, когда все компоненты $G - S$ являются полными графами. Тогда $S$ должен быть нарушителем Тутте, поскольку если $нечетное (G - S) \leq | С |$ , то мы могли бы найти идеальное паросочетание, сопоставив одну вершину из каждого нечетного компонента с вершиной из $S$ и соединив в пары все остальные вершины (это будет работать, если только $| V |$ не нечетно, но тогда $\emptyset$ является нарушителем Тутте).

Теперь предположим, что $—$ компонент $G - S$ и $x, y \in K$ — вершины такие, что $xy \notin E.$ K Пусть $x, a, b \in K$ — первые вершины кратчайшего $x, y$ пути в $K.$ - Это гарантирует, $xa, ab \in E$ и $xb \notin E.$ что Поскольку $a \notin S$ , существует вершина $c$ такая, $ac \notin E.$ что Исходя из реберной максимальности $G$ , мы определяем $M 1$ как идеальное паросочетание в $G + xb$ и $M 2$ как идеальное паросочетание в $G + ac$ . Заметим, что, конечно $xb \in M1,$ и $ac \in M2 же$ .

Пусть $P$ — максимальный путь в $G$ , который начинается из $c$ с ребром из $M 1$ и чьи ребра чередуются между $M 1$ и $M 2$ . Как может $закончиться P$ ? Если мы не дошли до «специальной» вершины, такой как $x, a$ или $b$ , мы всегда можем продолжить: $M$ c $2 -соответствует$ ca $,$ поэтому первое ребро $P$ не находится в $M 2$ , поэтому вторая вершина есть $M 2$ - соответствует другому краю, и мы продолжаем в том же духе.

Пусть $v$ обозначает последнюю вершину $P$ . Если последнее ребро $P$ находится в $M 1$ , то $v$ должно быть $a$ , так как в противном случае мы могли бы продолжить работу с ребром из $M 2$ (даже чтобы прийти к $x$ или $b$ ). В этом случае мы определяем $C := P + ac$ . Если последнее ребро $P$ находится в $M 2$ , то, несомненно, $v \in {x, b$ } по аналогичной причине, и мы определяем $C := P + va + ac$ .

Теперь $C$ — цикл в $G + ac$ четной длины со всеми остальными ребрами в $M 2$ . Теперь мы можем определить $M := M 2 ∆ C$ (где $∆$ — симметричная разность ) и получим совершенное паросочетание в $G$ , противоречие.

Эквивалентность формуле Тутте-Бержа

Формула Тутте-Бержа гласит, что размер максимального паросочетания графа $G=(V,E)$ равно $\min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right)/2$ . Эквивалентно, количество несовпадающих вершин в максимальном сопоставлении равно $\max _{U\subseteq V}\left(\operatorname {odd} (G-U)-|U|\right)$ .

Эта формула следует из теоремы Тутте вместе с наблюдением, что $G$ имеет соответствие размера $k$ тогда и только тогда, когда график $G^{(k)}$ получается добавлением $|V|-2k$ новые вершины, каждая из которых соединена с каждой исходной вершиной $G$ , имеет идеальное соответствие. Поскольку любой набор $X$ который отделяет $G^{(k)}$ в более чем $|X|$ компоненты должны содержать все новые вершины, (*) выполняется для $G^{(k)}$ тогда и только тогда, когда $k\leq \min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right)/2$ .

В бесконечных графах

Для связных бесконечных графов, которые локально конечны (каждая вершина имеет конечную степень), справедливо обобщение условия Тутта: такие графы имеют идеальные паросочетания тогда и только тогда, когда не существует конечного подмножества, удаление которого создает число конечных нечетных компонент, большее чем размер подмножества. ^[3]

См. также

Примечания

^ Ловас и Пламмер (1986) , с. 84; Бонди и Мерти (1976) , Теорема 5.4, с. 76.
^ Бонди и Мерти (1976) , стр. 76–78.
^ Тутте, WT (1950). «Факторизация локально конечных графов» . Канадский математический журнал . 2 : 44–49. дои : 10.4153/cjm-1950-005-2 . МР 0032986 . S2CID 124434131 .

Ссылки

Бонди, Дж.А.; Мурти, USR (1976). Теория графов с приложениями . Нью-Йорк: Американский паб Elsevier. компании ISBN 0-444-19451-7 .
Ловас, Ласло ; Пламмер, доктор медицины (1986). Теория соответствия . Амстердам: Северная Голландия. ISBN 0-444-87916-1 .

[1] Ловас и Пламмер (1986) , с. 84; Бонди и Мерти (1976) , Теорема 5.4, с. 76.

[bm-proof-2] Бонди и Мерти (1976) , стр. 76–78.

[3] Тутте, WT (1950). «Факторизация локально конечных графов» . Канадский математический журнал . 2 : 44–49. дои : 10.4153/cjm-1950-005-2 . МР 0032986 . S2CID 124434131 .

[1]

[2]

[3]