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

(Перевод с английского статьи "Extremal graph theory")
 
[[Файл:Turan 13-4.svg|thumb|[[Граф Турана]] T(n,r) является примером экстремального графа. Граф имеет максимальное возможное число рёбер для графов с n вершинами без (r+1)-[[ Клика (теория графов)|клик]]. На рисунке представлен граф T(13,4).]]
 
'''Экстремальная теория графов''' — это ветвь [[Теория графов|теории графов]]. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства [[Граф (математика)|графов]], удовлетворяющих определённым условиям. Экстремальность может относиться к различным [[Инвариант графа|инвариантам графов]], таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа {{sfn|Diestel|2010}}.
 
==Примеры==