Теорема Турана об экстремальном графе — различия между версиями
(Новая страница: «==Теорема Турана== '''Теорема Ту́рана''' дает сверху на количество ребер в графе, в котором н...») |
(нет различий)
|
Версия 20:52, 25 декабря 2017
Теорема Турана
Теорема Ту́рана дает сверху на количество ребер в графе, в котором нет полного n-дольного подграфа. Это классическая теорема из экстремальной теории графов. Она послужила образцом для большого количества подобных теорем, которые оценивают некоторые глобальные параметры, такие как хроматическое число, относительно тех или иных подструктур.
Впервые задачу сформулировал Пал Туран в 1941 году.
См. также
Источники информации
- Книга по дискре
