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

Примеры

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

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

История

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

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

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

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor }$

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

${\displaystyle \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 }$

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

${\displaystyle \left({\frac {1}{2}}+o(1)\right)n^{3/2}}$

рёбер.

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

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

${\displaystyle {\binom {n-1}{2}}}$

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

${\displaystyle \delta (G)=\min _{v\in G}d(v).}$

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

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

См. также

• Теория Рамсея

Примечания

Литература