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

В математической дисциплине теории графов теоремы Tutte , названной в честь Уильяма Томас Татта , является характеристикой графов с совершенным паросочетанием . Это обобщение теоремы Холла о браке с двудольных графов на произвольные. ^{[ требуется пояснение ]} Это частный случай формулы Тутте – Берже .

Теорема Тутте [ править ]

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

Доказательства [ править ]

Прямое доказательство [ править ]

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

{\ Displaystyle (*) \ qquad \ forall U \ substeq V, \ quad o (GU) \ Leq | U |}

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

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

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

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

Теперь предположим , что $K$ является компонентом $G - S$ и $х, у \in K$ являются вершинами такие , что $ху \notin E$ . Пусть $х, , б \in K$ первыми вершины на кратчайшем $х, у$ -path в $K$ . Это гарантирует , что $ха, абы \in E$ и $XB \notin E$ . Поскольку $a \notin S$ , существует вершина $c$ такая, что $переменный ток \notin E$ . Исходя из рёберной максимальности группы $G$ , мы определяем $M 1$ как совершенное паросочетание в $G + xb$ и $M 2$ как совершенное паросочетание в $G + ac$ . Заметим, что безусловно $xb \in M 1$ и $ac \in M 2$ .

Пусть $P$ - максимальный путь в $G,$ который начинается из $c$ ребром из $M 1$ и чьи ребра чередуются между $M 1$ и $M 2$ . Как может $P$ закончиться? Если мы не достигли «специальной» вершины, такой как $x, a$ или $b$ , мы всегда можем продолжить: $c$ является $M 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 + ва + ак$ .

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

Вывод из формулы Тутте-Берже [ править ]

Формула Тутте – Берже говорит, что размер максимального соответствия графа равен ${\ Displaystyle G = (V, E)}$ ${\frac {1}{2}}\min _{U\subseteq V}\left(|U|-\operatorname {odd} (G-U)+|V|\right)$

Состояние TUTTE является то , что для каждого , . Эквивалентно выражение внутри минимума - не меньше . Эквивалентно все выражение по крайней мере . $U\subseteq V$ ${\text{odd}}(G-U)\leq |U|$ $|V|$ $|V|/2$

Итак, условие Тутте выполняется, если и только если граф имеет совпадение по крайней мере по размеру , если и только если у графа есть идеальное совпадение. $|V|/2$

См. Также [ править ]

Заметки [ править ]

^ Lovász & Пламмер (1986) , стр. 84; Бонди и Мурти (1976) , теорема 5.4, с. 76.
^ Бонди и Мурти (1976) , стр. 76-78.

Ссылки [ править ]

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

[1] Lovász & Пламмер (1986) , стр. 84; Бонди и Мурти (1976) , теорема 5.4, с. 76.

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

[1]