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

16 байтів вилучено ,  1 рік тому
нема опису редагування
Немає опису редагування
Немає опису редагування
}}
 
'''Граф Турана''' ''T''(''n'',''r'') &nbsp;— це граф, утворений розкладанням ''n'' вершин на ''r'' підмножин, з якомога ближчим розміром, і вершини в цьому графі з'єднані ребром, якщо вони належать різним підмножинам. Граф буде мати <math>(n\,\bmod\,r)</math> підмножин розміром <math>\lceil n/r\rceil</math> і <math>r-(n\,\bmod\,r)</math> підмножин розміром <math>\lfloor n/r\rfloor</math>. Таким чином, це [[Багаточастковий граф|повний ''r''-частковий граф]]
 
: <math>K_{\lceil n/r\rceil, \lceil n/r\rceil, \ldots, \lfloor n/r\rfloor, \lfloor n/r\rfloor}.</math>
Графи Турана названо на честь [[Пал Туран|Пала Турана]], який використав їх для доведення [[Теорема Турана|теореми Турана]], важливого результату в [[Екстремальна теорія графів|екстремальній теорії графів]].
 
За [[Принцип Діріхле|принципом Діріхле]], будь-яка множина з ''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'', граф Турана є [[Симетричний граф|симетричним]] і [[Сильно регулярний граф|сильно регулярним]], хоча деякі автори вважають, що графи Турана є тривіальним випадком сильної регулярності і тому виключають їх з визначення строго регулярних графів.
 
Граф Турана <math>T(n,\lceil n/3\rceil)</math> має 3<sup>''a''</sup>2<sup>''b''</sup> [[Кліка (теорія графів)|найбільших клік]], де
 
== Інші властивості ==
Будь-який граф Турана є [[Кограф|кографомкограф]]ом. Таким чином, його можна утворити з окремих вершин послідовністю операцій [[Диз'юнктне об'єднання|диз'юнктного об'єднання]] і [[Доповнення графа|доповнення]]. Зокрема, таку послідовність можна почати утворенням усіх незалежних множин графаграфу Турана як диз'юнктного об'єднання ізольованих вершин. Тоді весь граф є доповненням диз'юнктного об'єднання доповнень цих незалежних множин.
 
Чао і Новацький (Chao, Novacky, 1982) показали, що графи Турана ''хроматично єдині'' &nbsp;— ніякі інші графи не мають таких самих [[Хроматичний многочлен|хроматичних многочленів]]. Нікіфоров (Nikiforov, 2005) використовував графи Турана для знаходження нижньої межі суми ''k''-х [[Власні вектори та власні числа|власних значень]] графаграфу і його доповнення.
 
Фолс, Повел і Сноїнк (Falls, Powell, Snoeyink) розробили ефективний алгоритм для пошуку кластерів ортологічних груп генів у геномі поданням даних як графаграфу і пошуком великих підграфів Турана.
 
Графи Турана мають також низку цікавих властивостей, пов'язаних з {{Не перекладено|Геометрична теорія графів|геометричною теорією графів|en|geometric graph theory}}. Пор і Вуд (Pór, Wood, 2005) дають нижню межу Ω((''rn'')<sup>3/4</sup>) будь-якого тривимірного вкладення графаграфу Турана. Вітсенгаузен (Witsenhausen, 1974) висловив гіпотезу, що найбільша сума квадратів відстаней між ''n'' точками всередині кулі '''R'''<sup>''d''</sup> одиничного діаметра досягається на конфігурації, утвореній вкладенням графаграфу Турана у вершини правильного симплекса.
 
Граф ''G'' з ''n'' вершинами є підграфом графаграфу Турана ''T''(''n'',''r'') [[тоді й лише тоді]], коли ''G'' допускає [[рівномірне розфарбування]] в ''r'' кольорів. Розкладання графаграфу Турана на незалежні множини відповідає розкладанню ''G'' на класи кольорів. Зокрема, граф Турана є єдиним максимальним графом з ''n'' вершинами з рівномірним розфарбуванням у ''r'' кольорів.
 
== Література ==