Теорема Турана об экстремальном графе — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Теорема Турана)
Строка 59: Строка 59:
 
Следовательно мы можем оценить количество ребер в <tex>G</tex>:
 
Следовательно мы можем оценить количество ребер в <tex>G</tex>:
  
−
<tex>|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)</tex>
+
<tex>|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)</tex>
  
 
Равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</tex>.
 
Равенство справа следует непосредственно из графа Турана <tex>T^{r-1}(n)</tex>.
Строка 73: Строка 73:
  
 
}}
 
}}
 +
 
==См. также==
 
==См. также==
 
*[[Раскраска графа]]
 
*[[Раскраска графа]]

Версия 22:33, 31 марта 2021

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

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

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

Впервые теорему сформулировал венгерский математик Пал Туран в [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]

См. также

Примечания

  1. ↑ Экстремальная теория графов

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Турана_об_экстремальном_графе&oldid=80768»