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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Граф Турана 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].

Історія

[ред. | ред. код]
Екстремальна теорія графів, в найстрогішому сенсі, є гілкою теорії графів, яку люблять і розвивають в Угорщині.

Bollobás, 2004

Екстремальна теорія графів виникла 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. а б Bollobás, 1998, с. 104.

Література

[ред. | ред. код]