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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Турана T(n,r) является примером экстремального графа. Граф имеет максимальное возможное число рёбер для графов с n вершинами без (r+1)-клик. На рисунке представлен граф T(13,4).

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

Примеры[править | править код]

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

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

История[править | править код]

Экстремальная теория графов, в самом строгом смысле, является ветвью теории графов, которую любят и развивают в Венгрии.

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

Плотность графа[править | править код]

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

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

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

рёбер.

Условия минимальной степени[править | править код]

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

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

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

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

См. также[править | править код]

Примечания[править | править код]

  1. Diestel, 2010.
  2. Bollobás, 2004, с. 9.
  3. Вообще говоря, свойство графа и инвариант — это одно и то же.
  4. 1 2 Bollobás, 1998, с. 104.

Литература[править | править код]