Просмотр кода страницы Экстремальная теория графов

[[Файл:Turan 13-4.svg|thumb|[[Граф Турана]] T(n,r) является примером экстремального графа. Граф имеет максимальное возможное число рёбер для графов с n вершинами без (r+1)-[[ Клика (теория графов)|клик]]. На рисунке представлен  граф T(13,4).]]

'''Экстремальная теория графов''' — это ветвь [[Теория графов|теории графов]]. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства [[Граф (математика)|графов]], удовлетворяющих определённым условиям. Экстремальность может относиться к различным [[Инвариант графа|инвариантам графов]], таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа{{sfn|Diestel|2010}}.

==Примеры==
Например, простым вопросом экстремальной теории графов является вопрос «Какие [[Дерево (теория графов)|ацикличные графы]] с ''n'' вершинами имеют максимальное число рёбер?» Экстремальными графами для этого вопроса будут [[Дерево (теория графов)|деревья]] с ''n'' вершинами, имеющие ''n''&nbsp;&minus;&nbsp;1 рёбер{{sfn|Bollobás|2004|с=9}}. Более общий типичный вопрос следующий: Если дано [[Инвариант графа|свойство графа]] ''P'', инвариант ''u''<ref>Вообще говоря, свойство графа и инвариант — это одно и то же.</ref> и  набор графов ''H'', мы хотим найти минимальное значение ''m'', такое, что любой граф из ''H'', который имеет ''u'', большее, чем ''m'', обладает свойством ''P''. В примере выше ''H'' было множеством графов с ''n'' вершинами, ''P'' было свойством быть циклом, а  ''u'' было числом рёбер в графе. Таким образом, любой граф с ''n'' вершинами и более чем с  ''n''&nbsp;&minus;&nbsp;1 рёбрами, должен содержать цикл.

Некоторые функциональные результаты в экстремальной теории графов — это вопросы упомянутых выше видов. Например, на вопрос, как много рёбер графа с ''n'' вершинами должно быть в графе, чтобы он обязательно содержал в качестве подграфа [[Клика (теория графов)|клику]] размера ''k'',  отвечает [[Теорема Турана|теорема Турана]]. Если вместо клик в аналогичном вопросе спрашиваются о полных многодольных графах, ответ даёт {{не переведено 5|теорема Эрдёша — Стоуна|||Erdős–Stone theorem}}.

==История==

{{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}}.

==Плотность графа==

Типичный результат экстремальной теории графов — [[теорема Турана]]. Теорема отвечает на следующий вопрос. Каково максимально возможное число рёбер в неориентированном графе ''G'' с ''n'' вершинами, не содержащем ''K''<sub>''3''</sub> (три вершины ''A'', ''B'', ''C'' с рёбрами ''AB'', ''AC'', ''BC'', то есть треугольник) в качестве подграфа? [[Полный двудольный граф]], в котором доли отличаются максимум на 1, является единственным экстремальным графом с этим свойством. Граф содержит
:<math> \left\lfloor \frac{n^2}{4} \right\rfloor</math> 
рёбер. Подобные вопросы ставились для различных других подграфов ''H'' вместо ''K''<sub>''3''</sub>. Например, [[задача Заранкиевича]] спрашивает о самом большом (по числу рёбер) графе, который не содержит фиксированного [[Полный двудольный граф|полного двудольного графа]] в качестве подграфа, а {{не переведено 5|теорема о чётных контурах|||even circuit theorem}} спрашивает о самом большом графе, не содержащем чётных [[Цикл (теория графов)|циклов]] фиксированной длины. [[Туран, Пал|Туран]] также нашёл (уникальный) самый большой граф, не содержащий ''K''<sub>''k''</sub>, который назван его именем, а именно [[граф Турана]]. Этот граф является [[Операции над графами|полным объединением]] "k-1" независимых множеств и имеет максимум 
:<math> \left\lfloor \frac{(k-2) n^2}{2(k-1)} \right\rfloor = \left\lfloor \left( 1- \frac{1}{k-1} \right) \frac{n^2}{2} \right\rfloor</math> 
рёбер. Наибольший граф с ''n'' вершинами, не содержащий ''C''<sub>''4''</sub>, имеет 
:<math> \left(\frac{1}{2}+o(1)\right) n^{3/2}</math> 
рёбер.

==Условия минимальной степени ==

Упомянутые теоремы дают условия для появления небольших объектов внутри (возможно) большого графа. В качестве противоположных экстремумов можно искать условие, которое вынуждает существование структуры, которая покрывает все вершины. Но граф с 
:<math> \binom{n-1}{2} </math>
рёбрами может иметь изолированные вершины, хотя почти все возможные рёбра присутствуют в графе, что означает, что даже очень плотные графы могут не иметь интересующую нас структуру, покрывающую все вершины. Простое условие, опирающееся на подсчёт рёбер, не даёт информации, как рёбра распределены в графе, так что часто такое условие даёт неинтересные результаты для очень больших структур. Вместо этого мы вводим понятие минимальной степени. Минимальная степень графа ''G'' определяется как 
:<math> \delta(G)=\min_{v\in G} d(v) . </math>
Задание большой минимальной степени удаляет возражение, что могут существовать «патологические» вершины. Если минимальная степень графа ''G'' равна 1, например, то не может быть изолированных вершин (даже если ''G'' содержит очень мало рёбер).

Классическим результатом является [[Гамильтонов граф|теорема Дирака]], которая утверждает, что любой граф ''G'' с ''n'' вершинами и минимальной степенью, не меньшей ''n/2'', содержит [[Гамильтонов граф|гамильтонов цикл]].

==См. также==
*[[Теория Рамсея]]

==Примечания==
{{примечания|2}}
==Литература==
{{refbegin|colwidth=30em}}
* {{книга
|ref=Bollobás
|автор=Béla Bollobás
|заглавие=Extremal Graph Theory
|издательство=[[Dover Publications]]
|место=New York
|isbn=978-0-486-43596-1
|год=2004
}}
* {{книга
|ref=Bollobás
|автор=Béla Bollobás
|заглавие=Modern Graph Theory
|издательство=[[Springer-Verlag]]
|место=Berlin, New York
|isbn=978-0-387-98491-9
|год=1998
|страницы=103–144
}}
* {{книга
|автор=Reinhard Diestel
|ref=Diestel
|заглавие=Graph Theory
|ссылка=http://diestel-graph-theory.com/index.html/
|издательство=Springer-Verlag
|место=Berlin, New York
|издание=4th
|isbn=978-3-642-14278-9
|год=2010
|страницы=169–198
}} {{Wayback|url=http://diestel-graph-theory.com/index.html/ |date=20170528023122 }}
**{{книга
|автор=Рейнгард Дистель
|заглавие=Теория графов
|место=Новосибирск
|издательство=Изд-во Ин-та математики
|год=2002
|isbn=5-86134-101-X УДК 519.17
}}
* {{статья
|автор=M. Simonovits
|ref=Simonovits
|заглавие=Slides from the Chorin summer school lectures, 2006.
|ссылка=http://www.renyi.hu/~miki/BerlinG.pdf
}}
{{refend}}

[[Категория:Экстремальная теория графов]]
{{rq|checktranslate|style}}