Теорема Турана об экстремальном графе

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Теорема Турана

Пример графа Турана при [math]n = 8, r = 4[/math]

Теорема Ту́рана (англ. Turán's theorem) — классическая теорема экстремальной теории графов. Она послужила образцом для большого количества подобных теорем, которые изучают, как наличие тех или иных подструктур влияет на некоторые глобальные параметры (хроматическое число).

Впервые теорему сформулировал венгерский математик Пал Туран в [math]1941[/math] году.

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

[math]K_n[/math] — полный граф на [math]n[/math] вершинах.

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

[math]ex(n, K_r)[/math] — максимальное количество ребер, которое может иметь граф на [math]n[/math] вершинах, не включая в себя [math]K_r[/math] как подграф.

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

Граф Турана [math]T^{r-1}(n)[/math] — полный [math](r - 1)[/math]-дольный граф на [math]n \gt r-1[/math] вершинах, доли которого по мощности отличаются не более чем на [math]1[/math]. Если количество вершин не превосходит количество долей ([math]n \leqslant r - 1[/math]), то [math]T^{r-1}(n) = K_n[/math].

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

[math]t_{r-1}(n)[/math] — количество ребер в [math]T^{r-1}(n)[/math].

Лемма:

Если [math]G[/math] — [math](r - 1)[/math]-дольный граф с максимальным количеством ребер, то [math]G = T^{r-1}(n)[/math].

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

[math]\triangleright[/math]

Докажем от противного. Пусть существует [math](r - 1)[/math]-дольный граф с максимальным числом ребер, который не является графом Турана. Обозначим его [math]G_m[/math]. Очевидно, что [math]G_m[/math] является полным [math](r - 1)[/math]-дольным. Так как [math]G_m \ne T^{r-1}(n) [/math], то в [math]G_m[/math] существуют доли [math]V_1[/math] и [math]V_2[/math], что [math]|V_1| - |V_2| \gt 1[/math]. Но тогда возьмем вершину [math]a \in V_1[/math] и перекинем ее в [math]V_2[/math]. Тогда количество вершин, которые не могут быть соседями [math]a[/math] уменьшилось с размером ее доли. Остальной граф не изменился, поэтому общее количество ребер увеличилось. Это противоречит предположению, что граф [math]G_m[/math] максимален по числу ребер. Значит лемма доказана.

[math]\triangleleft[/math]

Теорема:

Для всех натуральных чисел [math]r[/math], [math]n[/math], где [math]r \gt 1[/math], любой граф [math]G \nsubseteq K_r[/math] с [math]n[/math] вершинами и [math]ex(n, K_r)[/math] ребрами есть [math]T^{r-1}(n)[/math].

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

[math]\triangleright[/math]

Шаг индукции Применим индукцию по [math]n[/math]. База: При [math]n \leqslant r - 1[/math] имеем [math]G = K_n = T^{r-1}(n)[/math], что и утверждалось. База доказана. Шаг индукции: Пусть теперь [math]n \geqslant r[/math]. Поскольку [math]G[/math] реберно-максимален и не содержит подграфа [math]K_r[/math], то [math]G[/math] содержит подграф [math]K^{r-1}[/math]. Обозначим любой из них как [math]K[/math]. Тогда по индукционному предположению [math]G - K[/math] имеет не более [math]t_{r-1}(n - r + 1)[/math] ребер, а любая вершина [math]G - K[/math] имеет не более [math]r - 2[/math] соседей в [math]K.[/math] Следовательно мы можем оценить количество ребер в [math]G[/math]: [math]|E(G)| \leqslant \underbrace{t_{r-1}(n - r + 1)}_{G-K} + \underbrace{(n - r + 1)(r - 2)}_{(G-K) \rightleftarrows (K)} + \underbrace{{r-1 \choose 2}}_{K} = t_{r-1}(n); (1)[/math] Равенство справа следует непосредственно из графа Турана [math]T^{r-1}(n)[/math]. Поскольку [math]G[/math] экстремален для [math]K_r[/math], то в [math](1)[/math] имеет место равенство. Таким образом, любая вершина из [math]G - K[/math] имеет ровно [math]r - 2[/math] соседа в [math]K[/math] — точно так же, как и вершины [math]x_1,\cdots, x_{r-1}[/math] из самого [math]K[/math]. При [math]i = 1,\cdots, r-1[/math] пусть [math]V_i = \{v \in V(G) \mid vx_i \not\in E(G)\}[/math] есть множество всех вершин [math]G[/math], чьи [math]r - 2[/math] соседей в [math]K[/math] отличны от [math]x_i[/math]. Так как каждая вершина [math]G - K[/math] имеет ровно [math]r - 2[/math] соседа в [math]K[/math], то все [math]V_i[/math] не зависимы. При этом они в объединении дают [math]V(G)[/math] поскольку [math]K_r \nsubseteq G[/math]. Следовательно, граф [math]G[/math] является [math](r-1)[/math]-дольным. Тогда по лемме из предположения об экстремальности [math]G[/math] следует, что [math]G = T^{r-1}(n)[/math].

[math]\triangleleft[/math]

См. также

• Раскраска графа
• Двудольные графы

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

• Дистель, Рейнград. Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
• Экстремальная теория графов