Главная
Новости
Строительство
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




04.10.2022


04.10.2022


03.10.2022


03.10.2022


02.10.2022


02.10.2022


30.09.2022





Яндекс.Метрика

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

31.07.2022

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

Примеры

Например, простым вопросом экстремальной теории графов является вопрос «Какие ацикличные графы с 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, содержит гамильтонов цикл.


Имя:*
E-Mail:
Комментарий: