18
правок
Изменения
Нет описания правки
==Теорема Турана=='''Теорема Ту́рана''' (англ. ''Turán's theorem'') {{---}} классическая теорема экстремальной теории графов. Она послужила образцом для большого количества подобных теорем, которые изучают некоторые глобальные параметры, такие как [[Раскраска графа| хроматическое число]], относительно присутствия тех или иных подструктур.
Впервые задачу сформулировал Пал Туран в 1941 году.
{{Определение
|definition=
<tex>T^{r-1}(n)</tex> {{---}} единственный полный <tex>(r - 1)</tex>-дольный полный граф на <tex>n > r-1</tex> вершинах, доли которого по мощности не отличаются более чем на 1. Если
<tex>n \leqslant r - 1</tex>, то <tex>T^{r-1}(n) = K^n</tex>.
}}
{{Определение
|definition=
ex(n, r) {{---}} количество ребер в T^r(n).
}}
{{Теорема
|statement=
Для всем целых чисел r, n, где r > 1, любой граф G >= K^r с n вершинами и ex(n, K^r) ребрами есть T^r-1(n)
|proof=
доказательство (необязательно)
}}
==См. также==
==Источники информации==
* Книга по дискре
