Введение

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

Граф Турана, обозначаемый , является полным многодольным графом; он формируется путем разбиения множества из вершин на подмножеств, с максимально близкими по размеру, и соединением двух вершин ребром тогда и только тогда, когда они принадлежат разным подмножествам. Если и — это частное и остаток от деления на (то есть ), то граф имеет вид , а количество ребер равно. Для , это число ребер можно более кратко записать как: Граф имеет подмножеств размера и подмножеств размера ; каждая вершина имеет степень или . Это регулярный граф, если делится на (то есть, когда ).

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

Графы Турана названы в честь Паля Турана, который использовал их для доказательства теоремы Турана — важного результата в экстремальной теории графов. В силу принципа Дирихле, любое множество из r + 1 вершин в графе Турана содержит две вершины в одном и том же подмножестве разбиения; следовательно, граф Турана не содержит клику размера r + 1. Согласно теореме Турана, граф Турана имеет максимальное возможное число ребер среди всех (r + 1)-свободных от клики графов с n вершинами. Киваш и Судаков (2003) показали, что граф Турана также является единственным (r + 1)-свободным от клики графом порядка n, в котором любое подмножество из αn вершин порождает не менее ребер, если α достаточно близко к 1. Теорема Эрдеша — Стоуна расширяет теорему Турана, ограничивая число ребер в графе, не имеющем фиксированный граф Турана в качестве подграфа. С помощью этой теоремы аналогичные границы в экстремальной теории графов могут быть доказаны для любого исключенного подграфа, в зависимости от хроматического числа этого подграфа.

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

Несколько вариантов параметра r в графе Турана приводят к примечательным графам, которые изучались независимо. Граф Турана T(2n,n) можно сформировать, удалив совершенное паросочетание из полного графа K2n. Как было показано, этот граф имеет боксичность ровно n; он также известен как граф Робертса. Этот граф также является 1-скелетом n-мерного кросс-политопа; например, граф T(6,3) = K2,2,2 является октаэдрическим графом, графом правильного октаэдра. Если n пар идут на вечеринку, и каждый человек пожимает руку каждому, кроме своего партнера, то этот граф описывает множество рукопожатий, которые происходят; по этой причине он также называется графом коктейльной вечеринки. Граф Турана T(n,2) является полным двудольным графом и, когда n четно, графом Мура. Когда r является делителем n, граф Турана симметричен и сильно регулярен, хотя некоторые авторы считают графы Турана тривиальным случаем сильной регулярности и поэтому исключают их из определения сильно регулярного графа. Класс графов Турана может содержать экспоненциально много максимальных клик, что означает, что этот класс не является классом с малым числом клик. Например, граф Турана имеет 3a²b максимальных клик, где 3a + 2b = n и b ≤ 2; каждая максимальная клика формируется путем выбора одной вершины из каждого подмножества разбиения. Это наибольшее возможное число максимальных клик среди всех графов с n вершинами, независимо от количества ребер в графе (Moon и Moser, 1965); эти графы иногда называют графами Муна — Мозера.

Другие свойства

Каждый граф Турана является кографом; то есть, он может быть построен из отдельных вершин последовательностью операций дизъюнктного объединения и взятия дополнения. В частности, такая последовательность может начинаться с формирования каждого из независимых множеств графа Турана как дизъюнктного объединения изолированных вершин. Затем, весь граф является дополнением к дизъюнктному объединению дополнений этих независимых множеств. Чао и Новаки (1982) показали, что графы Турана хроматически уникальны: не существует других графов с одинаковыми хроматическими полиномами. Никифоров (2005) использует графы Турана для получения нижней оценки для суммы k-х собственных значений графа и его дополнения. Фолс, Пауэлл и Сноинк разработали эффективный алгоритм для поиска кластеров ортологических групп генов в геномных данных, представляя данные в виде графа и находя большие подграфы Турана. Графы Турана также обладают интересными свойствами, связанными с геометрической теорией графов. Pór и Wood (2005) приводят нижнюю границу Ω((rn)3/4) для объема любого трехмерного решетчатого вложения графа Турана. Витсенхаузен (1974) выдвинул предположение, что максимальная сумма квадратов расстояний между n точками с единичным диаметром в Rd достигается для конфигурации, образованной вложением графа Турана в вершины правильного симплекса. Граф G с n вершинами является подграфом графа Турана T(n,r) тогда и только тогда, когда G допускает равномерную раскраску r цветами. Разбиение графа Турана на независимые множества соответствует разбиению G на цветовые классы. В частности, граф Турана является единственным максимальным графом с n вершинами, допускающим равномерную раскраску r цветами.