Граф Турана: відмінності між версіями
[перевірена версія] | [перевірена версія] |
Немає опису редагування |
Немає опису редагування |
||
Рядок 14: | Рядок 14: | ||
}} |
}} |
||
'''Граф Турана''' ''T''(''n'',''r'') |
'''Граф Турана''' ''T''(''n'',''r'') — це граф, утворений розкладанням ''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> |
: <math>K_{\lceil n/r\rceil, \lceil n/r\rceil, \ldots, \lfloor n/r\rfloor, \lfloor n/r\rfloor}.</math> |
||
Рядок 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}}, [[Інтервальна розмірність графа|рамковість]] цього |
Граф Турана ''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> — це граф правильного [[октаедр]]а. Якщо ''n'' пар приходять на вечірку і кожна людина тисне руку всім, окрім свого партнера, то цей граф описує множину рукостискань. З цієї причини його також називають '''графом коктейль-вечірки'''. |
||
Граф Турана ''T''(''n'',2) |
Граф Турана ''T''(''n'',2) — це [[Повний дводольний граф|повний двочастковий граф]], і, якщо ''n'' парне, це [[граф Мура]]. Якщо ''r'' — це дільник ''n'', граф Турана є [[Симетричний граф|симетричним]] і [[Сильно регулярний граф|сильно регулярним]], хоча деякі автори вважають, що графи Турана є тривіальним випадком сильної регулярності і тому виключають їх з визначення строго регулярних графів. |
||
Граф Турана <math>T(n,\lceil n/3\rceil)</math> має 3<sup>''a''</sup>2<sup>''b''</sup> [[Кліка (теорія графів)|найбільших клік]], де |
Граф Турана <math>T(n,\lceil n/3\rceil)</math> має 3<sup>''a''</sup>2<sup>''b''</sup> [[Кліка (теорія графів)|найбільших клік]], де |
||
Рядок 42: | Рядок 42: | ||
== Інші властивості == |
== Інші властивості == |
||
Будь-який граф Турана є [[ |
Будь-який граф Турана є [[кограф]]ом. Таким чином, його можна утворити з окремих вершин послідовністю операцій [[Диз'юнктне об'єднання|диз'юнктного об'єднання]] і [[Доповнення графа|доповнення]]. Зокрема, таку послідовність можна почати утворенням усіх незалежних множин графу Турана як диз'юнктного об'єднання ізольованих вершин. Тоді весь граф є доповненням диз'юнктного об'єднання доповнень цих незалежних множин. |
||
Чао і Новацький (Chao, Novacky, 1982) показали, що графи Турана ''хроматично єдині'' |
Чао і Новацький (Chao, Novacky, 1982) показали, що графи Турана ''хроматично єдині'' — ніякі інші графи не мають таких самих [[Хроматичний многочлен|хроматичних многочленів]]. Нікіфоров (Nikiforov, 2005) використовував графи Турана для знаходження нижньої межі суми ''k''-х [[Власні вектори та власні числа|власних значень]] графу і його доповнення. |
||
Фолс, Повел і Сноїнк (Falls, Powell, Snoeyink) розробили ефективний алгоритм для пошуку кластерів ортологічних груп генів у геномі поданням даних як |
Фолс, Повел і Сноїнк (Falls, Powell, Snoeyink) розробили ефективний алгоритм для пошуку кластерів ортологічних груп генів у геномі поданням даних як графу і пошуком великих підграфів Турана. |
||
Графи Турана мають також низку цікавих властивостей, пов'язаних з {{Не перекладено|Геометрична теорія графів|геометричною теорією графів|en|geometric graph theory}}. Пор і Вуд (Pór, Wood, 2005) дають нижню межу Ω((''rn'')<sup>3/4</sup>) будь-якого тривимірного вкладення |
Графи Турана мають також низку цікавих властивостей, пов'язаних з {{Не перекладено|Геометрична теорія графів|геометричною теорією графів|en|geometric graph theory}}. Пор і Вуд (Pór, Wood, 2005) дають нижню межу Ω((''rn'')<sup>3/4</sup>) будь-якого тривимірного вкладення графу Турана. Вітсенгаузен (Witsenhausen, 1974) висловив гіпотезу, що найбільша сума квадратів відстаней між ''n'' точками всередині кулі '''R'''<sup>''d''</sup> одиничного діаметра досягається на конфігурації, утвореній вкладенням графу Турана у вершини правильного симплекса. |
||
Граф ''G'' з ''n'' вершинами є підграфом |
Граф ''G'' з ''n'' вершинами є підграфом графу Турана ''T''(''n'',''r'') [[тоді й лише тоді]], коли ''G'' допускає [[рівномірне розфарбування]] в ''r'' кольорів. Розкладання графу Турана на незалежні множини відповідає розкладанню ''G'' на класи кольорів. Зокрема, граф Турана є єдиним максимальним графом з ''n'' вершинами з рівномірним розфарбуванням у ''r'' кольорів. |
||
== Література == |
== Література == |
Версія за 14:15, 2 липня 2021
Граф Турана | |
---|---|
Граф Турана 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] розширює теорему Турана, обмежуючи число ребер у графі, який не має підграфом фіксованого графу Турана. Внаслідок цієї теореми в теорії екстремальних графів для будь-якого забороненого підграфу можна довести схожі межі, залежні від хроматичного числа підграфу.
Особливі випадки
Деякі величини параметра 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 (25 квітня). — С. 139–143. — DOI: .
- 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 (25 квітня). — С. 139–153. — DOI: .
- J. W. Moon, L. Moser. On cliques in graphs // Israel Journal of Mathematics. — 1965. — Т. 3 (25 квітня). — С. 23–28. — DOI: .
- Vladimir Nikiforov. Eigenvalue problems of Nordhaus-Gaddum type. — 2005. — 25 квітня. — 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:
- 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 (25 квітня). — С. 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 (25 квітня). — С. 1100–1101. — DOI: .
Посилання
- Weisstein, Eric W. Cocktail Party Graph(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Граф октаедра(англ.) на сайті Wolfram MathWorld.
- Weisstein, Eric W. Граф Турана(англ.) на сайті Wolfram MathWorld.