Изменения

==Теорема Турана==[[Файл:Turan example.png|200px|thumb|right|Пример графа Турана при <tex>n = 8, r = 4</tex>]]'''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов<ref>[https://ru. wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов]</ref>.Она послужила образцом для большого количества подобных теорем, которые изучают , как наличие тех или иных подструктур влияет на некоторые глобальные параметры, такие как ([[Раскраска графа| хроматическое число]], относительно присутствия тех или иных подструктур).

Впервые задачу теорему сформулировал венгерский математик Пал Туран в <tex>1941 </tex> году. {{Определение|definition=<tex>K_n</tex> {{---}} полный граф на <tex>n</tex> вершинах.}} {{Определение|definition=<tex>ex(n, K_r)</tex> {{---}} максимальное количество ребер, которое может иметь граф на <tex>n</tex> вершинах, не включая в себя <tex>K_r</tex> как подграф.}} {{Определение|definition='''Граф Турана''' <tex>T^{r-1}(n)</tex> {{---}} полный <tex>(r - 1)</tex>-[[Двудольные графы|дольный]] граф на <tex>n > r-1</tex> вершинах, доли которого по мощности отличаются не более чем на <tex>1</tex>. Если количество вершин не превосходит количество долей (<tex>n \leqslant r - 1</tex>), то <tex>T^{r-1}(n) = K_n</tex>.}} {{Определение|definition=<tex>t_{r-1}(n)</tex> {{---}} количество ребер в <tex>T^{r-1}(n)</tex>.}}  {{Лемма|statement=Если <tex>G</tex> {{---}} <tex>(r - 1)</tex>-дольный граф с максимальным количеством ребер, то <tex>G = T^{r-1}(n)</tex>.|proof=Докажем от противного. Пусть существует <tex>(r - 1)</tex>-дольный граф с максимальным числом ребер, который не является графом Турана.Обозначим его <tex>G_m</tex>.Очевидно, что <tex>G_m</tex> является полным <tex>(r - 1)</tex>-дольным.Так как <tex>G_m \ne T^{r-1}(n) </tex>, то в <tex>G_m</tex> существуют доли <tex>V_1</tex> и <tex>V_2</tex>, что <tex>|V_1| - |V_2| > 1</tex>.Но тогда возьмем вершину <tex>a \in V_1</tex> и перекинем ее в <tex>V_2</tex>. Тогда количество вершин, которые не могут быть соседями <tex>a</tex> уменьшилось с размером ее доли. Остальной граф не изменился, поэтому общее количество ребер увеличилось.Это противоречит предположению, что граф <tex>G_m</tex> максимален по числу ребер. Значит лемма доказана.}}{{Теорема|statement=Для всех натуральных чисел <tex>r</tex>, <tex>n</tex>, где <tex>r > 1</tex>, любой граф <tex>G \nsubseteq K_r</tex> с <tex>n</tex> вершинами и <tex>ex(n, K_r)</tex> ребрами есть <tex>T^{r-1}(n)</tex>.|proof=[[Файл:Turan theorem induction step.png|300px|thumb|left|Шаг индукции]]Применим индукцию по <tex>n</tex>. '''База:''' При <tex>n \leqslant r - 1</tex> имеем <tex>G = K_n = T^{r-1}(n)</tex>, что и утверждалось. База доказана. '''Шаг индукции:''' Пусть теперь <tex>n \geqslant r</tex>.Поскольку <tex>G</tex> реберно-максимален и не содержит подграфа <tex>K_r</tex>, то <tex>G</tex> содержит подграф <tex>K^{r-1}</tex>.Обозначим любой из них как <tex>K</tex>.Тогда по индукционному предположению <tex>G - K</tex> имеет не более <tex>t_{r-1}(n - r + 1)</tex> ребер, а любая вершина <tex>G - K</tex> имеет не более <tex>r - 2</tex> соседей в <tex>K.</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>T^{r-1}(n)</tex>. Поскольку <tex>G</tex> экстремален для <tex>K_r</tex>, то в <tex>(1)</tex> имеет место равенство.Таким образом, любая вершина из <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex> {{---}} точно так же, как и вершины <tex>x_1,\cdots, x_{r-1}</tex> из самого <tex>K</tex>. При <tex>i = 1,\cdots, r-1</tex> пусть <tex>V_i = \{v \in V(G) \mid vx_i \not\in E(G)\}</tex> есть множество всех вершин <tex>G</tex>, чьи <tex>r - 2</tex> соседей в <tex>K</tex> отличны от <tex>x_i</tex>.Так как каждая вершина <tex>G - K</tex> имеет ровно <tex>r - 2</tex> соседа в <tex>K</tex>, то все <tex>V_i</tex> не зависимы.При этом они в объединении дают <tex>V(G)</tex> поскольку <tex>K_r \nsubseteq G</tex>.Следовательно, граф <tex>G</tex> является <tex>(r-1)</tex>-дольным.Тогда по лемме из предположения об экстремальности <tex>G</tex> следует, что <tex>G = T^{r-1}(n)</tex>. }}

* Книга по дискре''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.*[https://ru.wikipedia.org/wiki/%D0%AD%D0%BA%D1%81%D1%82%D1%80%D0%B5%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2 Экстремальная теория графов] [[Категория: Раскраски графов]][[Категория: Алгоритмы и структуры данных]]