Граф Турана

Граф Турана T(n,r) — це граф, утворений розкладанням n вершин на r підмножин, з якомога ближчим розміром, і вершини в цьому графі з'єднані ребром, якщо вони належать різним підмножинам. Граф буде мати $(nmodr)$ підмножин розміром $\lceil n/r\rceil$ і $r-(nmodr)$ підмножин розміром $\lfloor n/r\rfloor$. Таким чином, це повний r-частковий граф

$K_{\lceil n/r\rceil ,\lceil n/r\rceil ,\dots ,\lfloor n/r\rfloor ,\lfloor n/r\rfloor }.$

Кожна вершина має степінь або $n-\lceil n/r\rceil$, або $n-\lfloor n/r\rfloor$. Кількість ребер дорівнює

$\frac{1}{2}(n^2-(nmodr)\lceil n/r{\rceil }^2-(r-(nmodr))\lfloor n/r{\rfloor }^2)\le (1-\frac{1}{r})\frac{n^2}{2}.$

Граф є регулярним, якщо n ділиться на r.

Теорема Турана

Шаблон:Докладніше Графи Турана названо на честь Пала Турана, який використав їх для доведення теореми Турана, важливого результату в екстремальній теорії графів.

За принципом Діріхле, будь-яка множина з r + 1 вершин у графі Турана включає дві вершини з однієї й тієї ж частки графа. Таким чином, граф Турана не містить кліки розміру r + 1. Згідно з теоремою Турана, граф Турана має максимально можливе число ребер серед усіх графів без клік розміру r + 1, що мають n вершин. Киваш і Судаков (Keevash, Sudakov, 2003) показали, що граф Турана є єдиним графом без клік розміру r + 1, що має порядок n, у якому будь-яка підмножина з αn вершин має щонайменше $\frac{r-1}{2r}(2\alpha -1)n^2$ ребер, якщо α досить близьке до 1. Шаблон:Не перекладено розширює теорему Турана, обмежуючи число ребер у графі, який не має підграфом фіксованого графа Турана. Внаслідок цієї теореми в теорії екстремальних графів для будь-якого забороненого підграфа можна довести схожі межі, залежні від хроматичного числа підграфа.

Особливі випадки

Октаедр, вершини і ребра якого утворюють граф Турана T(6,3).

Деякі величини параметра r графів Турана призводять до чудових графів, які вивчаються окремо.

Граф Турана T(2n,n) можна отримати видаленням досконалого парування з повного графа K_2n. Як показав Робертс Шаблон:Harvard citation, рамковість цього графа дорівнює рівно n. Цей граф іноді називають графом Робертса. Цей граф є також 1-Шаблон:Не перекладено n-вимірного кографа. Наприклад, граф T(6,3) = K_2,2,2 — це граф правильного октаедра. Якщо n пар приходять на вечірку і кожна людина тисне руку всім, окрім свого партнера, то цей граф описує множину рукостискань. З цієї причини його також називають графом коктейль-вечірки.

Граф Турана T(n,2) — це повний двочастковий граф, і, якщо n парне, це граф Мура. Якщо r — це дільник n, граф Турана є симетричним і сильно регулярним, хоча деякі автори вважають, що графи Турана є тривіальним випадком сильної регулярності і тому виключають їх з визначення строго регулярних графів.

Граф Турана $T(n,\lceil n/3\rceil )$ має 3^a2^b найбільших клік, де 3a + 2b = n та b ≤ 2. Кожна найбільша кліка утворюється вибором однієї вершини з кожної частки. Це число найбільших клік є найбільшим можливим серед усіх графів з n вершинами, незалежно від числа ребер у графі (Мун і Мозер, 1965). Ці графи іноді називають графами Муна-Мозера.

Інші властивості

Будь-який граф Турана є кографом. Таким чином, його можна утворити з окремих вершин послідовністю операцій диз'юнктного об'єднання і доповнення. Зокрема, таку послідовність можна почати утворенням усіх незалежних множин графа Турана як диз'юнктного об'єднання ізольованих вершин. Тоді весь граф є доповненням диз'юнктного об'єднання доповнень цих незалежних множин.

Чао і Новацький (Chao, Novacky, 1982) показали, що графи Турана хроматично єдині — ніякі інші графи не мають таких самих хроматичних многочленів. Нікіфоров (Nikiforov, 2005) використовував графи Турана для знаходження нижньої межі суми k-х власних значень графа і його доповнення.

Фолс, Повел і Сноїнк (Falls, Powell, Snoeyink) розробили ефективний алгоритм для пошуку кластерів ортологічних груп генів у геномі поданням даних як графа і пошуком великих підграфів Турана.

Графи Турана мають також низку цікавих властивостей, пов'язаних з Шаблон:Не перекладено. Пор і Вуд (Pór, Wood, 2005) дають нижню межу Ω((rn)^3/4) будь-якого тривимірного вкладення графа Турана. Вітсенгаузен (Witsenhausen, 1974) висловив гіпотезу, що найбільша сума квадратів відстаней між n точками всередині кулі R^d одиничного діаметра досягається на конфігурації, утвореній вкладенням графа Турана у вершини правильного симплекса.

Граф G з n вершинами є підграфом графа Турана T(n,r) тоді й лише тоді, коли G допускає рівномірне розфарбування в r кольорів. Розкладання графа Турана на незалежні множини відповідає розкладанню G на класи кольорів. Зокрема, граф Турана є єдиним максимальним графом з n вершинами з рівномірним розфарбуванням у r кольорів.

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Шаблон:Mathworld
• Шаблон:Mathworld
• Шаблон:Mathworld