Граф Турана: відмінності між версіями

Жодних змін в розмірі ,  4 місяці тому
нема опису редагування
(вікіфікація)
Немає опису редагування
Графи Турана названо на честь [[Пал Туран|Пала Турана]], який використав їх для доведення [[Теорема Турана|теореми Турана]], важливого результату в [[Екстремальна теорія графів|екстремальній теорії графів]].
 
За [[Принцип Діріхле|принципом Діріхле]], будь-яка множина з ''r'' + 1 вершин у графі Турана включає дві вершини з однієї й тієї ж частки графаграфу. Таким чином, граф Турана не містить [[Кліка (теорія графів)|кліки]] розміру ''r'' + 1. Згідно з теоремою Турана, граф Турана має максимально можливе число ребер серед усіх графів без клік розміру ''r'' + 1, що мають ''n'' вершин. Киваш і Судаков (Keevash, Sudakov, 2003) показали, що граф Турана є єдиним графом без клік розміру ''r'' + 1, що має порядок ''n'', у якому будь-яка підмножина з α''n'' вершин має щонайменше <math>\frac{r\,{-}\,1}{2r}(2\alpha -1)n^2</math> ребер, якщо α досить близьке до 1. {{Не перекладено|Теорема Ердеша — Стоуна||en|Erdős–Stone theorem}} розширює теорему Турана, обмежуючи число ребер у графі, який не має підграфом фіксованого графу Турана. Внаслідок цієї теореми в теорії екстремальних графів для будь-якого забороненого підграфу можна довести схожі межі, залежні від [[Розфарбовування графів|хроматичного числа]] підграфу.
 
== Особливі випадки ==
Деякі величини параметра ''r'' графів Турана призводять до чудових графів, які вивчаються окремо.
 
Граф Турана ''T''(2''n'',''n'') можна отримати видаленням [[Парування (теорія графів)|досконалого парування]] з [[Повний граф|повного графаграфу]] ''K''<sub>2''n''</sub>. Як показав Робертс {{Harvard citation|Roberts|1969}}, [[Інтервальна розмірність графаграфу|рамковість]] цього графу дорівнює рівно ''n''. Цей граф іноді називають ''графом Робертса''. Цей граф є також 1-{{Не перекладено|Скелет (топологія)|скелетом|en|Skeleton (topology)}} ''n''-вимірного [[кограф]]а. Наприклад, граф ''T''(6,3) = ''K''<sub>2,2,2</sub>&nbsp;— це граф правильного [[октаедр]]а. Якщо ''n'' пар приходять на вечірку і кожна людина тисне руку всім, окрім свого партнера, то цей граф описує множину рукостискань. З цієї причини його також називають '''графом коктейль-вечірки'''.
 
Граф Турана ''T''(''n'',2)&nbsp;— це [[Повний дводольний граф|повний двочастковий граф]], і, якщо ''n'' парне, це [[граф Мура]]. Якщо ''r''&nbsp;— це дільник ''n'', граф Турана є [[Симетричний граф|симетричним]] і [[Сильно регулярний граф|сильно регулярним]], хоча деякі автори вважають, що графи Турана є тривіальним випадком сильної регулярності і тому виключають їх з визначення строго регулярних графів.
 
== Інші властивості ==
Будь-який граф Турана є [[кограф]]ом. Таким чином, його можна утворити з окремих вершин послідовністю операцій [[Диз'юнктне об'єднання|диз'юнктного об'єднання]] і [[Доповнення графаграфу|доповнення]]. Зокрема, таку послідовність можна почати утворенням усіх незалежних множин графу Турана як диз'юнктного об'єднання ізольованих вершин. Тоді весь граф є доповненням диз'юнктного об'єднання доповнень цих незалежних множин.
 
Чао і Новацький (Chao, Novacky, 1982) показали, що графи Турана ''хроматично єдині''&nbsp;— ніякі інші графи не мають таких самих [[Хроматичний многочлен|хроматичних многочленів]]. Нікіфоров (Nikiforov, 2005) використовував графи Турана для знаходження нижньої межі суми ''k''-х [[Власні значення|власних значень]] графу і його доповнення.