Перегляд вихідного коду сторінки Граф Турана

{{Граф
 | name = Граф Турана
 | image = [[Image:Turan 13-4.svg|180px]]
 | image_caption = Граф Турана T(13,4)
 | namesake = [[Пал Туран]]
 | vertices = ''n''
 | edges = ~<math>\frac{(r - 1) n^2}{2 r}</math>
 | radius = <math>\left\{\begin{array}{ll}\infty & r = 1\\ 2 & r \le n/2\\ 1 & \text{otherwise}\end{array}\right.</math>
 | diameter = <math>\left\{\begin{array}{ll}\infty & r = 1\\ 1 & r = n\\ 2 & \text{otherwise}\end{array}\right.</math>
 | girth = <math>\left\{\begin{array}{ll}\infty & r = 1 \vee (n \le 3 \wedge r \le 2)\\ 4 & r = 2\\ 3 & \text{otherwise}\end{array}\right.</math>
 | chromatic_number = ''r''
 | chromatic_index =
 | notation = ''T''(''n'',''r'')
}}

'''Граф Турана''' ''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>

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

: <math>\frac{1}{2}(n^2 - (n\,\bmod\,r)\lceil n/r\rceil^2 - (r-(n\,\bmod\,r))\lfloor n/r\rfloor^2) \leq \left(1-\frac1r\right)\frac{n^2}{2}.</math>

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

== Теорема Турана ==
{{Докладніше}}
Графи Турана названо на честь [[Пал Туран|Пала Турана]], який використав їх для доведення [[Теорема Турана|теореми Турана]], важливого результату в [[Екстремальна теорія графів|екстремальній теорії графів]].

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

== Особливі випадки ==
[[Файл:Octahedron.svg|міні|150x150пкс|Октаедр, вершини і ребра якого утворюють граф Турана ''T''(6,3).]]
Деякі величини параметра ''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> [[Кліка (теорія графів)|найбільших клік]], де
3''a'' + 2''b'' = ''n'' та ''b'' ≤ 2. Кожна найбільша кліка утворюється вибором однієї вершини з кожної частки. Це число найбільших клік є найбільшим можливим серед усіх графів з ''n'' вершинами, незалежно від числа ребер у графі (Мун і Мозер, 1965). Ці графи іноді називають '''графами Муна-Мозера'''.

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

Чао і Новацький (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'' кольорів.

== Література ==
* {{Стаття|author=C. Y. Chao, G. A. Novacky|title=On maximally saturated graphs|видання=Discrete Mathematics|том=41|pages=139–143|date=1982|doi=10.1016/0012-365X(82)90200-X|ref=Chao, Novacky|issue=2}}
* {{Стаття|title=Computing high-stringency COGs using Turán type graphs|author=Craig Falls, Bradford Powell, Jack Snoeyink|url=http://www.cs.unc.edu/~snoeyink/comp145/cogs.pdf|ref=Falls, Powell, Snoeyink|accessdate=4 січня 2021|archivedate=17 квітня 2021|archiveurl=https://web.archive.org/web/20210417231826/http://www.cs.unc.edu/~snoeyink/comp145/cogs.pdf}}
* {{Стаття|title=Local density in graphs with forbidden subgraphs|author=Peter Keevash, Benny Sudakov|видання=Combinatorics, Probability and Computing|date=2003|том=12|pages=139–153|doi=10.1017/S0963548302005539|issue=2|ref=Keevash, Sudakov}}
* {{Стаття|author=J. W. Moon, L. Moser|title=On cliques in graphs|видання=Israel Journal of Mathematics|том=3|pages=23–28|date=1965|doi=10.1007/BF02760024|ref=Moon, Moser}}
* {{Стаття|author=Vladimir Nikiforov|title=Eigenvalue problems of Nordhaus-Gaddum type|date=2005|arxiv=math.CO/0506260|ref=Nikiforov}}
* {{Книга
|автор = Attila Pór, David R Wood
|заголовок = [[International Symposium on Graph Drawing|Proc. Int. Symp. Graph Drawing (GD 2004)]]
|видавництво = Lecture Notes in Computer Science no. 3383, Springer-Verlag
|рік = 2005
|сторінки = 395–402
|doi = 10.1007/b105810
|ref = Pór, Wood
}}
* {{Книга
|автор = F. S. Roberts
|заголовок = Recent Progress in Combinatorics
|видавництво = Academic Press
|рік = 1969
|сторінки = 301–310
|ref = Roberts
}}
* {{Стаття|author=P. Turán|title=On an extremal problem in graph theory|видання=Matematiko Fizicki Lapok|том=48|date=1941|pages=436–452|ref=Turán}}
* {{Стаття|author=H. S. Witsenhausen|title=On the maximum of the sum of squared distances under a diameter constraint|date=1974|видання=[[American Mathematical Monthly]]|pages=1100–1101|том=81|doi=10.2307/2319046|issue=10|publisher=The American Mathematical Monthly, Vol. 81, No. 10|ref=Witsenhausen}}

== Посилання ==
* {{Mathworld||urlname=CocktailPartyGraph|title=Cocktail Party Graph}}
* {{Mathworld||urlname=OctahedralGraph|title=Граф октаедра}}
* {{Mathworld||urlname=TuranGraph|title=Граф Турана}}

[[Категорія:Параметричні сімейства графів]]
[[Категорія:Екстремальна теорія графів]]