Экстремальная теория графов: различия между версиями

{{Quote box|quote=Экстремальная теория графов, в самом строгом смысле, является ветвью теории графов, которую любят и развивают в Венгрии.|source={{harvnb|Bollobás|2004}}|width=300px}}
 
Экстремальная теория графов возникла в 1941, когда Туран доказал [[Теорема Турана|свою теорему]], определяющую графы порядка ''n'', не содержащие полного графа ''K''<sub>''k''</sub> порядка k, и экстремальные относительно размера (то есть, с как можно меньшим числом рёбер) {{sfn|Bollobás|1998|с=104}}. Следующим ключевым годом стал 1975, когда Семереди доказал [[Теорема Семереди|свою теорему]], важный инструмент для атаки на экстремальные задачи {{sfn|Bollobás|1998|с=104}}.
 
==Плотность графа==