Изменения
Нет описания правки
==Теорема Турана==
[[Файл: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_m</tex> максимален по числу ребер.
Значит <tex>G = T^{r-1}(n)</tex>лемма доказана.
}}
{{Теорема
*[[Раскраска графа]]
*[[Двудольные графы]]
==Примечания==
<references />
==Источники информации==
*''Дистель, Рейнград.'' Теория графов: Пер. с англ. — Новосибирск: Изд-во Ин-та математики, 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 Экстремальная теория графов]
[[Категория: Раскраски графов]]
[[Категория: Алгоритмы и структуры данных]]
