18
правок
Изменения
Нет описания правки
Она послужила образцом для большого количества подобных теорем, которые изучают некоторые глобальные параметры, такие как [[Раскраска графа| хроматическое число]], относительно присутствия тех или иных подструктур.
Впервые задачу сформулировал Пал Туран в <tex>1941 </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>. Через <tex> t_{r-1}(n) </tex> обозначим количество ребер в <tex>T^{r-1}(n)</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>V_1</tex> в <tex>V_2</tex> и количество ребер увеличится.
Это противоречит предположению, что граф <tex>G_m</tex> максимален по числу ребер. Значит <tex>G = T^{r-1}(n)</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>T^{r-1}(n)</tex> {{---}} единственный <tex>(r-1)</tex>-дольный граф с <tex>n</tex> вершинами и максимальными числом ребер, наше утверждение, что <tex>G = T^{r-1}(n)</tex>, следует из предположения об экстремальности <tex>G</tex>.
}}
*[[Двудольные графы]]
==Источники информации==
*''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
