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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
(вікіфікація)
Немає опису редагування
Рядок 28: Рядок 28:
Графи Турана названо на честь [[Пал Туран|Пала Турана]], який використав їх для доведення [[Теорема Турана|теореми Турана]], важливого результату в [[Екстремальна теорія графів|екстремальній теорії графів]].
Графи Турана названо на честь [[Пал Туран|Пала Турана]], який використав їх для доведення [[Теорема Турана|теореми Турана]], важливого результату в [[Екстремальна теорія графів|екстремальній теорії графів]].


За [[Принцип Діріхле|принципом Діріхле]], будь-яка множина з ''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'' + 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}} розширює теорему Турана, обмежуючи число ребер у графі, який не має підграфом фіксованого графу Турана. Внаслідок цієї теореми в теорії екстремальних графів для будь-якого забороненого підграфу можна довести схожі межі, залежні від [[Розфарбовування графів|хроматичного числа]] підграфу.


== Особливі випадки ==
== Особливі випадки ==
Рядок 34: Рядок 34:
Деякі величини параметра ''r'' графів Турана призводять до чудових графів, які вивчаються окремо.
Деякі величини параметра ''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''(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'', граф Турана є [[Симетричний граф|симетричним]] і [[Сильно регулярний граф|сильно регулярним]], хоча деякі автори вважають, що графи Турана є тривіальним випадком сильної регулярності і тому виключають їх з визначення строго регулярних графів.
Граф Турана ''T''(''n'',2)&nbsp;— це [[Повний дводольний граф|повний двочастковий граф]], і, якщо ''n'' парне, це [[граф Мура]]. Якщо ''r''&nbsp;— це дільник ''n'', граф Турана є [[Симетричний граф|симетричним]] і [[Сильно регулярний граф|сильно регулярним]], хоча деякі автори вважають, що графи Турана є тривіальним випадком сильної регулярності і тому виключають їх з визначення строго регулярних графів.
Рядок 42: Рядок 42:


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


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

Версія за 20:05, 28 грудня 2021

Граф Турана
Turan 13-4.svg
Граф Турана T(13,4)
Названо на честь Пал Туран
Вершин n
Ребер ~
Радіус
Діаметр
Обхват
Хроматичне число r
Позначення T(n,r)

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

Кожна вершина має степінь або , або . Кількість ребер дорівнює

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

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

Докладніше: [[|]]

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

За принципом Діріхле, будь-яка множина з r + 1 вершин у графі Турана включає дві вершини з однієї й тієї ж частки графу. Таким чином, граф Турана не містить кліки розміру r + 1. Згідно з теоремою Турана, граф Турана має максимально можливе число ребер серед усіх графів без клік розміру r + 1, що мають n вершин. Киваш і Судаков (Keevash, Sudakov, 2003) показали, що граф Турана є єдиним графом без клік розміру r + 1, що має порядок n, у якому будь-яка підмножина з αn вершин має щонайменше ребер, якщо α досить близьке до 1. Теорема Ердеша — Стоуна[en] розширює теорему Турана, обмежуючи число ребер у графі, який не має підграфом фіксованого графу Турана. Внаслідок цієї теореми в теорії екстремальних графів для будь-якого забороненого підграфу можна довести схожі межі, залежні від хроматичного числа підграфу.

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

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

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

Граф Турана T(2n,n) можна отримати видаленням досконалого парування з повного графу K2n. Як показав Робертс (Roberts, 1969), рамковість цього графу дорівнює рівно n. Цей граф іноді називають графом Робертса. Цей граф є також 1-скелетом[en] n-вимірного кографа. Наприклад, граф T(6,3) = K2,2,2 — це граф правильного октаедра. Якщо n пар приходять на вечірку і кожна людина тисне руку всім, окрім свого партнера, то цей граф описує множину рукостискань. З цієї причини його також називають графом коктейль-вечірки.

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

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

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

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

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

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

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

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

Література

  • C. Y. Chao, G. A. Novacky. On maximally saturated graphs // Discrete Mathematics. — 1982. — Т. 41, вип. 2 (1 липня). — С. 139–143. — DOI:10.1016/0012-365X(82)90200-X.
  • Craig Falls, Bradford Powell, Jack Snoeyink. Computing high-stringency COGs using Turán type graphs.
  • Peter Keevash, Benny Sudakov. Local density in graphs with forbidden subgraphs // Combinatorics, Probability and Computing. — 2003. — Т. 12, вип. 2 (1 липня). — С. 139–153. — DOI:10.1017/S0963548302005539.
  • J. W. Moon, L. Moser. On cliques in graphs // Israel Journal of Mathematics. — 1965. — Т. 3 (1 липня). — С. 23–28. — DOI:10.1007/BF02760024.
  • Vladimir Nikiforov. Eigenvalue problems of Nordhaus-Gaddum type. — 2005. — 1 липня. — arXiv:math.CO/0506260.
  • Attila Pór, David R Wood. Proc. Int. Symp. Graph Drawing (GD 2004). — Lecture Notes in Computer Science no. 3383, Springer-Verlag, 2005. — С. 395–402. — DOI:10.1007/b105810.
  • F. S. Roberts. Recent Progress in Combinatorics. — Academic Press, 1969. — С. 301–310.
  • P. Turán. On an extremal problem in graph theory // Matematiko Fizicki Lapok. — 1941. — Т. 48 (1 липня). — С. 436–452.
  • H. S. Witsenhausen. On the maximum of the sum of squared distances under a diameter constraint // American Mathematical Monthly. — The American Mathematical Monthly, Vol. 81, No. 10, 1974. — Т. 81, вип. 10 (1 липня). — С. 1100–1101. — DOI:10.2307/2319046.

Посилання