Екстремальна теорія графів — Вікіпедія

Екстремальна теорія графів — це гілка теорії графів. Екстремальна теорія графів вивчає екстремальні (максимальні або мінімальні) властивості графів, які задовольняють певним умовам. Екстремальність може стосуватися різних інваріантів графів, таких як порядок, розмір або обхват. В абстрактнішому сенсі, теорія вивчає, як глобальні властивості графу впливають на локальні підструктури графу^[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, що не містять повного графу K_k порядку k, і екстремальні відносно розміру (тобто з якомога меншим числом ребер)^[4]. Наступним ключовим роком став 1975, коли Семереді довів свою теорему, важливий інструмент для атаки на екстремальні задачі^[4].

Щільність графу[ред. | ред. код]

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

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

ребер. Подібні питання ставилися для різних інших підграфів H замість K₃. Наприклад, задача Заранкієвича запитує про найбільший (за числом ребер) граф, який не містить підграфом фіксованого повного двочасткового графу, а теорема про парні контури^[en] запитує про найбільший граф, який не містить парних циклів фіксованої довжини. Туран також знайшов (унікальний) найбільший граф, що не містить 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, містить гамільтонів цикл.

Див. також[ред. | ред. код]

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

Примітки[ред. | ред. код]

Література[ред. | ред. код]

п о р Розділи математики огляд[en] переліки тем Галузі Алгебра елементарна лінійна полілінійна абстрактна Теорія груп геометрична комбінаторна обчислювальна Алгоритми Арифметика / Теорія чисел адитивна алгебрична аналітична Геометрія дискретна алгебрична біраціональна диференціальна синтетична скінченна Диференціальні рівняння / Динамічні системи Комбінаторика адитивна алгебрична арифметична геометрична многогранників нумераційна топологічна Математика та мистецтво Математична логіка Математична статистика Математична фізика Обчислення / Аналіз Оптимізація Опуклий аналіз Рекреаційна математика Статистика Теорія графів алгебрична екстремальна спектральна Теорія ігор Теорія інформації Теорія ймовірності Теорія категорій Теорія керування Теорія Лі Теорія множин Теорія порядку Теорія представлень Топологія загальна алгебрична диференціальна Тригонометрія Функціональний аналіз Чисельний аналіз Підрозділи Чиста Прикладна Дискретна Обчислювальна Експериментальна   Категорія   Портал