График Туран

График Туран
Граф Турана T(13,4)
Назван в честь	Пал Туран
Вершины	$n$
Края	~ $\left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}$
Радиус	$\left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.$
Диаметр	$\left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{otherwise}}\end{array}}\right.$
Обхват	$\left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{otherwise}}\end{array}}\right.$
Хроматическое число	$r$
Обозначения	$T(n,r)$
Таблица графиков и параметров

Граф Турана , обозначаемый $T(n,r)$, — полный многодольный граф ; он формируется путем множества разделения $n$ вершины в $r$ подмножества с максимально равными размерами, а затем соединяя две вершины ребром тогда и только тогда, когда они принадлежат разным подмножествам. Где $q$ и $s$ это частное и остаток от деления $n$ к $r$ (так $n=qr+s$), график имеет вид $K_{q+1,q+1,\ldots ,q,q}$, а число ребер равно

$\left(1-{\frac {1}{r}}\right){\frac {n^{2}-s^{2}}{2}}+{s \choose 2}$.

Для $r\leq 7$, это количество ребер можно более кратко выразить как $\left\lfloor \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}\right\rfloor$. На графике есть $s$ подмножества размера $q+1$, и $r-s$ подмножества размера $q$; каждая вершина имеет степень $n-q-1$ или $n-q$. Это регулярный граф, если $n$ делится на $r$ (т.е. когда $s=0$).

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

Основная статья: теорема Турана

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

По принципу ячейки каждый набор из r + 1 вершин в графе Турана включает две вершины в одном и том же подмножестве разбиения; следовательно, граф Турана не содержит клики размера r + 1. Согласно теореме Турана, граф Турана имеет максимально возможное количество ребер среди всех ( r + 1)-безкликовых графов с n вершинами. Киваш и Судаков (2003) показывают, что граф Турана также является единственным ( r + 1)-кликовым графом порядка n , в котором каждое подмножество из α n вершин охватывает не менее ${\frac {r\,{-}\,1}{3r}}(2\alpha -1)n^{2}$ ребра, если α достаточно близко к 1. Теорема Эрдеша-Стоуна расширяет теорему Турана, ограничивая количество ребер в графе, который не имеет фиксированного графа Турана в качестве подграфа. С помощью этой теоремы аналогичные оценки в экстремальной теории графов можно доказать для любого исключенного подграфа, в зависимости от хроматического числа подграфа.

Особые случаи

Октаэдр , ребра , 3- перекрестный многогранник и вершины которого образуют K _2,2,2 , граф Турана T (6,3). В этой гранецентрированной проекции несвязным вершинам присвоен одинаковый цвет.

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

Граф Турана T (2 n , n ) может быть сформирован путем удаления идеального паросочетания из полного графа K _{2 n} . Как показал Робертс (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 ^а 2 ^б максимальные клики , где3 a + 2 b = n и b ≤ 2; каждая максимальная клика формируется путем выбора одной вершины из каждого подмножества разбиения. Это наибольшее возможное количество максимальных клик среди всех графов с n вершинами, независимо от количества ребер в графе; эти графики иногда называют графиками Муна – Мозера .

Другие объекты недвижимости

Каждый граф Турана является кографом ; то есть он может быть образован из отдельных вершин с помощью последовательности операций непересекающегося объединения и дополнения . В частности, такая последовательность может начинаться с формирования каждого из независимых множеств графа Турана как непересекающегося объединения изолированных вершин. Тогда общий граф является дополнением непересекающегося объединения дополнений этих независимых множеств.

Чао и Новаки (1982) показывают, что графы Турана хроматически уникальны : никакие другие графы не имеют таких же хроматических многочленов . Никифоров (2005) использует графы Турана для получения нижней оценки суммы k -х собственных значений графа и его дополнения.

Фоллс, Пауэлл и Снойинк (2003) разработали эффективный алгоритм поиска кластеров ортологичных групп генов в данных генома, представляя данные в виде графа и осуществляя поиск больших подграфов Турана.

Графы Турана также обладают некоторыми интересными свойствами, связанными с геометрической теорией графов . Пор и Вуд (2005) дают нижнюю оценку Ω(( rn ) ^3/4 ) от объема любого трехмерного сеточного вложения графа Турана. Витсенхаузен (1974) предполагает, что максимальная сумма квадратов расстояний среди n точек с единичным диаметром в R ^д , достигается для конфигурации, образованной вложением графа Турана в вершины регулярного симплекса.

Граф с n вершинами G является подграфом графа Турана T ( n , r ) тогда и только тогда, когда G допускает справедливую раскраску в r цветов. Разделение графа Турана на независимые множества соответствует разделению G на цветовые классы. В частности, граф Турана — это единственный максимальный граф из n вершин с справедливой раскраской в ​​r -цвета.

Ссылки

• Чао, Калифорния; Новаки, Джорджия (1982). «О максимально насыщенных графах» . Дискретная математика . 41 (2): 139–143. дои : 10.1016/0012-365X(82)90200-X .
• Фолс, Крейг; Пауэлл, Брэдфорд; Снойинк, Джек (2003). «Расчет COG высокой строгости с использованием графов типа Туран» (PDF) .
• Киваш, Питер; Судаков, Бенни (2003). «Локальная плотность в графах с запрещенными подграфами» (PDF) . Комбинаторика, теория вероятностей и вычисления . 12 (2): 139–153. дои : 10.1017/S0963548302005539 . S2CID   17854032 .
• Мун, Дж.В.; Мозер, Л. (1965). «О кликах в графах». Израильский математический журнал . 3 : 23–28. дои : 10.1007/BF02760024 . S2CID   9855414 .
• Никифоров, Владимир (2007). «Задачи о собственных значениях типа Нордхауса-Гаддума» . Дискретная математика . 307 (6): 774–780. arXiv : math.CO/0506260 . дои : 10.1016/j.disc.2006.07.035 .
• Пор, Аттила; Вуд, Дэвид Р. (2005). «Нет-три в ряд-в-3D». Учеб. Межд. Симп. Рисование графика (GD 2004) . Конспекты лекций по информатике нет. 3383, Шпрингер-Верлаг. стр. 395–402. дои : 10.1007/b105810 . hdl : 11693/27422 .
• Робертс, Ф.С. (1969). Тутте, WT (ред.). «О коробочности и кубичности графа». Недавний прогресс в комбинаторике : 301–310.
• Туран, П. (1941). «Об одной экстремальной задаче теории графов». Статьи по математике и физике . 48 : 436–452.
• Витсенхаузен, HS (1974). «О максимуме суммы квадратов расстояний при ограничении диаметра». Американский математический ежемесячник . 81 (10): 1100–1101. дои : 10.2307/2319046 . JSTOR   2319046 .

Внешние ссылки

• Вайсштейн, Эрик В. «График коктейльной вечеринки» . Математический мир .
• Вайсштейн, Эрик В. «Октаэдрический граф» . Математический мир .
• Вайсштейн, Эрик В. «График Турана» . Математический мир .