График Турана

Сбалансированный полный многодольный граф

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

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

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

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

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

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

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

Октаэдр , 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 , граф Турана симметричен и сильно регулярен , хотя некоторые авторы считают графы Турана тривиальным случаем сильной регулярности и поэтому исключают их из определения сильно регулярного графа.

Класс графов Турана может иметь экспоненциально много максимальных клик, то есть в этом классе не так уж мало клик . Например, граф Турана имеет 3 ^a 2 ^b максимальных клики , где 3 a  + 2 b  =  n и b  ≤ 2; каждая максимальная клика формируется путем выбора одной вершины из каждого подмножества разбиения. Это наибольшее возможное количество максимальных клик среди всех графов с n вершинами, независимо от количества ребер в графе (Мун и Мозер, 1965); эти графики иногда называют графиками Муна – Мозера . ${\displaystyle T(n,\lceil n/3\rceil )}$

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

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

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

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

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

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

Рекомендации

• Чао, Калифорния; Новаки, Джорджия (1982). «О максимально насыщенных графах». Дискретная математика . 41 (2): 139–143. дои : 10.1016/0012-365X(82)90200-X .
• Фолс, Крейг; Пауэлл, Брэдфорд; Снуинк, Джек. «Расчет COG высокой строгости с использованием графов типа Туран» (PDF) . {{cite journal}}: Требуется цитировать журнал |journal=( помощь )
• Киваш, Питер; Судаков, Бенни (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). «Egy gráfelméleti szélsőértékfeladatról (Об экстремальной задаче теории графов)». Математика – это физика . 48 : 436–452.
• Витсенхаузен, HS (1974). «О максимуме суммы квадратов расстояний при ограничении диаметра». Американский математический ежемесячник . 81 (10): 1100–1101. дои : 10.2307/2319046. JSTOR  2319046.

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

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