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

Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа.

Примеры

Например, простым вопросом экстремальной теории графов является вопрос «Какие ацикличные графы с n вершинами имеют максимальное число рёбер?» Экстремальными графами для этого вопроса будут деревья с n вершинами, имеющие n − 1 рёбер. Более общий типичный вопрос следующий: Если дано свойство графа P, инвариант u и набор графов H, мы хотим найти минимальное значение m, такое, что любой граф из H, который имеет u, большее, чем m, обладает свойством P. В примере выше H было множеством графов с n вершинами, P было свойством быть циклом, а u было числом рёбер в графе. Таким образом, любой граф с n вершинами и более чем с n − 1 рёбрами, должен содержать цикл.

Некоторые функциональные результаты в экстремальной теории графов — это вопросы упомянутых выше видов. Например, на вопрос, как много рёбер графа с n вершинами должно быть в графе, чтобы он обязательно содержал в качестве подграфа клику размера k, отвечает теорема Турана. Если вместо клик в аналогичном вопросе спрашиваются о полных многодольных графах, ответ даёт теорема Эрдёша — Стоуна.

История

Экстремальная теория графов возникла в 1941, когда Туран доказал свою теорему, определяющую графы порядка n, не содержащие полного графа Kk порядка k, и экстремальные относительно размера (то есть с как можно меньшим числом рёбер). Следующим ключевым годом стал 1975, когда Семереди доказал свою теорему, важный инструмент для атаки на экстремальные задачи.

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

Типичный результат экстремальной теории графов — теорема Турана. Теорема отвечает на следующий вопрос. Каково максимально возможное число рёбер в неориентированном графе G с n вершинами, не содержащем K3 (три вершины A, B, C с рёбрами AB, AC, BC, то есть треугольник) в качестве подграфа? Полный двудольный граф, в котором доли отличаются максимум на 1, является единственным экстремальным графом с этим свойством. Граф содержит

⌊ n 2 4 ⌋ {displaystyle leftlfloor {frac {n^{2}}{4}} ight floor }

рёбер. Подобные вопросы ставились для различных других подграфов H вместо K3. Например, задача Заранкиевича спрашивает о самом большом (по числу рёбер) графе, который не содержит фиксированного полного двудольного графа в качестве подграфа, а теорема о чётных контурах спрашивает о самом большом графе, не содержащем чётных циклов фиксированной длины. Туран также нашёл (уникальный) самый большой граф, не содержащий Kk, который назван его именем, а именно граф Турана. Этот граф является полным объединением "k-1" независимых множеств и имеет максимум

⌊ ( k − 2 ) n 2 2 ( k − 1 ) ⌋ = ⌊ ( 1 − 1 k − 1 ) n 2 2 ⌋ {displaystyle leftlfloor {frac {(k-2)n^{2}}{2(k-1)}} ight floor =leftlfloor left(1-{frac {1}{k-1}} ight){frac {n^{2}}{2}} ight floor }

рёбер. Наибольший граф с n вершинами, не содержащий C4, имеет

( 1 2 + o ( 1 ) ) n 3 / 2 {displaystyle left({frac {1}{2}}+o(1) ight)n^{3/2}}

рёбер.

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

Упомянутые теоремы дают условия для появления небольших объектов внутри (возможно) большого графа. В качестве противоположных экстремумов можно искать условие, которое вынуждает существование структуры, которая покрывает все вершины. Но граф с

( n − 1 2 ) {displaystyle {inom {n-1}{2}}}

рёбрами может иметь изолированные вершины, хотя почти все возможные рёбра присутствуют в графе, что означает, что даже очень плотные графы могут не иметь интересующую нас структуру, покрывающую все вершины. Простое условие, опирающееся на подсчёт рёбер, не даёт информации, как рёбра распределены в графе, так что часто такое условие даёт неинтересные результаты для очень больших структур. Вместо этого мы вводим понятие минимальной степени. Минимальная степень графа G определяется как

δ ( G ) = min v ∈ G d ( v ) . {displaystyle delta (G)=min _{vin G}d(v).}

Задание большой минимальной степени удаляет возражение, что могут существовать «патологические» вершины. Если минимальная степень графа G равна 1, например, то не может быть изолированных вершин (даже если G содержит очень мало рёбер).

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