Граф Турана T ( n , r ) является полным многодольным графом, образованным путем разбиения набора из n вершин на r подмножеств с максимально равными размерами и соединения двух вершин ребром тогда и только тогда, когда они принадлежат разным подмножествам. Где с участием , график будет иметь подмножества размера , а также подмножества размера . То есть это полный r -раздельный граф. Каждая вершина имеет степень либо или же . Количество ребер
График Турана | |
---|---|
Названный в честь | Пал Туран |
Вершины | п |
Края | ~ |
Радиус | |
Диаметр | |
Обхват | |
Хроматическое число | р |
Обозначение | Т ( п , г ) |
Таблица графиков и параметров |
Это правильный граф, если n делится на r .
Теорема Турана
Графы Турана названы в честь Пала Турана , который использовал их для доказательства теоремы Турана , важного результата в экстремальной теории графов .
По принципу «голубятни», каждый набор из r + 1 вершин в графе Турана включает две вершины в одном и том же подмножестве разбиения; следовательно, граф Турана не содержит клики размера r + 1. Согласно теореме Турана, граф Турана имеет максимально возможное число ребер среди всех ( r + 1) -кликовых графов с n вершинами. Кееваш и Судаков (2003) показывают, что граф Турана также является единственным ( r + 1) -кликовым графом порядка n, в котором каждое подмножество из α n вершин охватывает не менееребер, если α достаточно близко к 1. Теорема Эрдеша – Стоуна расширяет теорему Турана, ограничивая количество ребер в графе, не имеющем фиксированного графа Турана в качестве подграфа. С помощью этой теоремы аналогичные оценки в экстремальной теории графов могут быть доказаны для любого исключенного подграфа, в зависимости от хроматического числа подграфа.
Особые случаи
Несколько вариантов выбора параметра r в графе Турана привели к появлению примечательных графов, которые были изучены независимо.
Граф Турана T (2 n , n ) может быть сформирован путем удаления полного совпадения из полного графа K 2 n . Как показал Робертс (1969) , этот граф имеет прямоугольность ровно n ; его иногда называют графом Робертса . Этот график также 1- скелет из п - мерного поперечного многогранника ; например, граф 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 вершинами независимо от количества ребер в графе (Moon and Moser 1965); эти графы иногда называют графами Муна – Мозера .
Прочие свойства
Каждый граф Турана - это кограф ; то есть, он может быть сформирован из отдельных вершин последовательностью непересекающихся операций объединения и дополнения . В частности, такая последовательность может начинаться с формирования каждого из независимых наборов графа Турана как несвязного объединения изолированных вершин. Тогда общий граф является дополнением несвязного объединения дополнений этих независимых множеств.
Чао и Новаки (1982) показывают, что графы Турана хроматически уникальны : ни один другой граф не имеет таких же хроматических полиномов . Никифоров (2005) использует графы Турана для получения нижней оценки суммы k- х собственных значений графа и его дополнения.
Фоллс, Пауэлл и Сноиинк разрабатывают эффективный алгоритм для поиска кластеров ортологичных групп генов в данных генома путем представления данных в виде графа и поиска больших подграфов Турана.
Графы Турана также обладают некоторыми интересными свойствами, связанными с геометрической теорией графов . Пор и Вуд (2005) дают нижнюю оценку Ω (( rn ) 3/4 ) объема любого трехмерного сеточного вложения графа Турана. Витсенхаузен (1974) предполагает, что максимальная сумма квадратов расстояний среди n точек с единичным диаметром в R d достигается для конфигурации, образованной вложением графа Турана в вершины регулярного симплекса.
П -vertex граф G является подграфом из Турана графа Т ( п , г ) тогда и только тогда , когда G допускает равноправную окраску с г цветами. Разделение графа Турана на независимые множества соответствует разбиению G на классы цветов. В частности, граф Турана является единственным графом с максимальными n- вершинами и r -цветной равноправной раскраской.
Рекомендации
- Chao, CY; Новацкий, Г.А. (1982). «О максимально насыщенных графах». Дискретная математика . 41 (2): 139–143. DOI : 10.1016 / 0012-365X (82) 90200-X .
- Falls, Крейг; Пауэлл, Брэдфорд; Snoeyink, Джек. «Вычисление COG высокой строгости с использованием графиков типа Турана» (PDF) . Цитировать журнал требует
|journal=
( помощь ) - Кееваш, Питер; Судаков, Бенни (2003). «Локальная плотность в графах с запрещенными подграфами» (PDF) . Комбинаторика, теория вероятностей и вычисления . 12 (2): 139–153. DOI : 10.1017 / S0963548302005539 .
- Луна, JW; Мозер, Л. (1965). «По кликам в графах». Израильский математический журнал . 3 : 23–28. DOI : 10.1007 / BF02760024 . S2CID 9855414 .
- Никифоров, Владимир (2005). "Задачи на собственные значения типа Нордхауза-Гаддума". arXiv : math.CO/0506260 .
- Пор, Аттила; Вуд, Дэвид Р. (2005). «Нет-тройка в строке в 3D». Proc. Int. Symp. Графический рисунок (GD 2004) . Конспект лекций по информатике No. 3383, Springer-Verlag. С. 395–402. DOI : 10.1007 / b105810 . ЛВП : 11693/27422 .
- Робертс, Ф. С. (1969). Тутте, WT (ред.). «О коробчатости и кубичности графа». Последние достижения в комбинаторике : 301–310.
- Туран, П. (1941). «Egypt gráfelméleti szélsőértékfeladatról (Об одной экстремальной задаче в теории графов)». Matematikai és Fizikai Lapok . 48 : 436–452.
- Витсенхаузен, HS (1974). «О максимуме суммы квадратов расстояний при ограничении диаметра». Американский математический ежемесячник . 81 (10): 1100–1101. DOI : 10.2307 / 2319046 . JSTOR 2319046 .
Внешние ссылки
- Вайсштейн, Эрик В. "График коктейльной вечеринки" . MathWorld .
- Вайсштейн, Эрик В. «Октаэдрический граф» . MathWorld .
- Вайсштейн, Эрик В. "График Турана" . MathWorld .