Граф Турана

Граф Турана
Граф Турана
Назван в честь	Пал Туран
Вершин	n
Рёбер
Радиус
Диаметр
Обхват
Хроматическое число	r
Обозначение	= T(n,r)
	Медиафайлы на Викискладе

Граф Турана T(n,r) — это граф, образованный разложением n вершин на r подмножеств, с как можно близким размером, и вершины в этом графе соединены ребром, если они принадлежат разным подмножествам. Граф будет иметь $(n\,{\bmod {\,}}r)$ подмножеств размером $\lceil n/r\rceil$ и $r-(n\,{\bmod {\,}}r)$ подмножеств размером $\lfloor n/r\rfloor$ . Таким образом, это полный r-дольный граф

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

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

{\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-{\frac {1}{r}}\right){\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. Как показал Робертс (Roberts 1969), рамочность этого графа равна в точности 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 цветов.

Примечания

Литература

C. Y. Chao, G. A. Novacky. On maximally saturated graphs // Discrete Mathematics. — 1982. — Т. 41, вып. 2. — С. 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. — С. 139–153. — doi:10.1017/S0963548302005539.
J. W. Moon, L. Moser. On cliques in graphs // Israel Journal of Mathematics. — 1965. — Т. 3. — С. 23–28. — doi:10.1007/BF02760024.
Vladimir Nikiforov. Eigenvalue problems of Nordhaus-Gaddum type. — 2005. — 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. — С. 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. — С. 1100–1101. — doi:10.2307/2319046. — .

Ссылки

Weisstein, Eric W. Cocktail Party Graph (англ.) на сайте Wolfram MathWorld.
Weisstein, Eric W. Octahedral Graph (англ.) на сайте Wolfram MathWorld.
Weisstein, Eric W. Turán Graph (англ.) на сайте Wolfram MathWorld.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.