1632
правки
Изменения
м
rollbackEdits.php mass rollback
==Теорема Турана==
[[Файл: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> году.
Следовательно мы можем оценить количество ребер в <tex>G</tex>:
<tex>|E(G)| \leqslant \underbrace{t_{r-1}(n - r + 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>.
}}
==См. также==
*[[Раскраска графа]]
*[[Двудольные графы]]
==Примечания==
<references />
==Источники информации==
*''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 2002. — 166-170 стр. — ISBN 5-86134-101-X.
