Полный граф

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна.[1] По́лный ориенти́рованный графориентированный граф, в котором каждая пара различных вершин соединена парой ребер с противоположными ориентациями.[2] Принято считать, что теория графов берет свое начало с решения Леонардом Эйлером задачи о семи кёнигсбергских мостах, датированного 1736 годом, однако изображения полных графов, вершины которых располагаются в вершинах правильных многоугольников, встречаются ещё в 13 веке, в работе Раймунда Луллия.[3] Подобные рисунки иногда называют мистическими розами.[4]

Полный граф
K7, полный граф с 7 вершинами
K7, полный граф с 7 вершинами
Вершин n
Рёбер
Диаметр
Обхват
Автоморфизмы n! (Sn)
Хроматическое число n
Хроматический индекс n если n - нечётное,
иначе n − 1
Спектр
Свойства
Обозначение Kn
Логотип Викисклада Медиафайлы на Викискладе
Полный граф на рисунке из труда Ars Magna Раймунда Луллия.

Обычно полный граф с вершинами обозначается через . Некоторые источники утверждают, что буква в этом обозначении является сокращением от немецкого слова нем. komplett,[5] в переводе на русский – «полный, целый», однако оригинальное название полного графа на немецком, нем. vollständiger Graph, не содержит буквы . По другой версии, такое обозначение полному графу было дано в честь Казимежа Куратовского, подчеркивая его вклад в развитие теории графов.[6]

Комбинаторные свойства

править
  • Полный граф с   вершинами имеет   рёбер, это треугольное число.
  • Полный граф с   вершинами является регулярным графом степени  .
  • Любой полный граф является своей максимальной кликой.
  • Граф   является  -связным[англ.].
  • Дополнение графа   – это пустой граф, то есть граф без рёбер.
  • Полный граф, каждое ребро которого снабжено ориентацией, называется турниром.
  • В полном графе не может быть независимого множества более чем из одной вершины.[7]
  • Пусть  , а   – семейство деревьев ограниченных степеней, где для любого   число вершин дерева   равно  . Тогда граф   можно разложить на деревья  , то есть существуют попарно рёберно-непересекающиеся копии графов   в графе  , и каждое ребро графа   принадлежит хотя бы одной из этих копий.[8]
  • Число различных путей между двумя выделенными вершинами в полном графе   вычисляется[9] по формуле  , где через   обозначена постоянная Эйлера, и
     
  • Индексы Хосойи (полные числа паросочетаний) полного графа являются телефонными числами[англ.] ( -ое телефонное число – это число различных вариантов, которыми из   человек можно выбрать набор пар людей, которые будут одновременно созваниваться друг с другом по телефону; в частности можно выбрать пустой набор), причем на полных графах реализуются максимально возможные значения индекса Хосойи для  -вершинного графа.[10] Эти индексы образуют последовательность
    1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... последовательность A000085 в OEIS.
  • Число совершенных паросочетаний графа   с чётным   определяется с помощью двойного факториала и равняется  .[11]
  • Теорема Рамсея: Для любых   натуральных чисел   в любой  -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с   вершинами для некоторого цвета  . В частности, для любых   и  , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из   вершин, либо полный белый подграф из   вершин.[12]
  • Теорема Турана: Обозначим через   максимальное количество рёбер, которое может иметь граф с   вершинами, не содержащий подграфа, изоморфного  . Тогда, если  , где   — остаток от деления   на  , то этот максимум равен   Среди всех графов на   вершинах, не содержащих подграфа  , этот максимум по количеству рёбер достигается на графе  , определяемом следующим образом. Пусть   это граф с   вершинами, разобьём все вершины на   «почти равных» групп (то есть возьмём   групп по   вершине и   групп по   вершин, если   с остатком  ) и соединим рёбрами все пары вершин из разных групп. Таким образом получим  -дольный граф.[13]
  • Теорема Кэли о числе деревьев: Число остовных деревьев в полном графе   равно  [14]

Геометрические и топологические свойства

править

Число пересечений

править

Известна верхняя оценка на число пересечений полного графа, а именно  . Впервые, в конце пятидесятых, вопрос о существовании такой оценки выдвинул Энтони Хилл,[15] известный британский художник-абстракционист. Ему удалось разработать несколько особых методов изображения полных графов, позволивших в дальнейшем эффективно исследовать их числа пересечений. Один из таких методов известен как «рисунок на алюминиевой банке», а другой – как «изображения Харари-Хилла».[16] Анализируя эти методы изображения математикам Блажеку и Коману удалось подтвердить[17] оценку Хилла для всех полных графов в 1964 году. Стоит отметить, что Хилл выдвинул куда более сильную гипотезу, а именно  . Эта гипотеза известна как гипотеза Хилла и на данный момент подтверждена только для нескольких малых  .[18] Гипотезу Хилла иногда называют гипотезой Гая, в честь британского математика Ричарда Гая, в чьей работе[19] за 1960 год содержатся прямые намеки на данный вопрос, или гипотезой Харари-Хилла, так как работа[20] Энтони Хилла и Фрэнка Харари за 1963 год, видимо, самая ранняя опубликованная математическая статья, содержащая точную формулировку этой гипотезы.[21] Полные графы   при   являются планарными, то есть их число пересечений равно 0. В 1972 году Гай показал,[22] что гипотеза Хилла верна для всех  , а в 2007 году Шэнджунь Пэн и Брюс Рихтер подтвердили[23] гипотезу Хилла для  . В 2015 году Дэн Макуиллан, Шэнджунь Пэн и Брюс Рихтер выяснили,[24] что   является нечетным числом, лежащим между 219 и 225 включительно. Вся известная на данный момент информация о точных значениях чисел пересечений полных графов представлена в таблице ниже.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  или  

Кроме того, в 1969 году Гай получил[25] нижнюю оценку на число пересечений полного графа, а именно  . При этом, ещё в 1960 году он обнаружил,[19] что существует предел  , где  , а в 2007 году Этьен де Клерк, Дмитрий Пасечник и Александр Схрейвер выяснили,[26] что верна оценка

 .

Число прямолинейных пересечений

править

Для   и   число прямолинейных пересечений графа  , которое обычно обозначается через  , совпадает с его обыкновенным числом пересечений. Однако, число прямолинейных пересечений графа   равно  , тогда как  .[20] В 2001 году Алекс Бродский, Стефан Дуроше и Эллен Гетнер[англ.] выяснили,[27] что число прямолинейных пересечений графа   равно 62, при  . На данный момент точные значения   известны для   и  . Суть точного вычисления заключается в нахождении соответствующих (и совпадающих) нижних и верхних оценок. Нижние оценки для   были построены[28] совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром в 2012 году, нижняя оценка для   построена[29] совместно математиками Марио Сетина, Сесаром Эрнандес-Велесом, Хесусом Леаньосом и Кристобалем Вильялобос Гильеном в 2012 году, а все верхние оценки получены австрийским математиком Освином Айххольцером[30]. Кроме того, Айххольцер опубликовал[30] на своем сайте суммарную информацию обо всех известных на данный момент нижних и верхних оценках на   вплоть до  . Ниже приведена таблица с соответствующими оценками для  .

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  или  
 ,   или  
 

В 1994 году Эдвард Р. Шайнерман[англ.] и Герберт С. Уилф[англ.] обнаружили[31] неожиданную связь между числом прямолинейных пересечений графа   и задачей Сильвестра "о четырех точках" из вероятностной геометрии.[32] Пусть   — открытое множество на плоскости с конечной мерой Лебега. Обозначим через   вероятность того, что если в   равномерно и случайно выбраны четыре точки независимо друг от друга, то их выпуклая оболочка является четырехугольником, а через   – инфимум значений   по всем таким  . Тогда верно равенство

 

где   обозначает соответствующий биномиальный коэффициент. Продолжительное время уточнялись[33] верхняя и нижняя оценки на константу  , и на данный момент лучшая нижняя[34] и лучшая верхняя[28] оценки получены совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром, и составляют

 
 
Книжное вложение с тремя страницами для графа  

Планарность и книжная толщина

править

Графы с   по   являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф   и, следовательно, не удовлетворяют критерию Понтрягина — Куратовского.[35]

При   граф   является 1-планарным графом, но при   граф   не является 1-планарным.[36]

Книжная толщина графа   равна  . Для любых   граф   имеет книжную толщину в точности  .[37]

Симплексы и многогранники

править
 
Интерактивное изображение многогранника Часара. Водите мышью влево и вправо чтобы поворачивать SVG изображение.

Полный граф образуется из вершин и ребер (n-1)-симплекса. Так, например, геометрически   образует множество вершин и ребер треугольника,   – тетраэдра и так далее. Объединение всех семи вершин и двадцати одного ребра многогранника Часара, топологически эквивалентного тору, образует полный граф  .

Граф 2-смежностного многогранника является полным графом.

Зацепленность и заузленность

править

Граф   не имеет незацепленного вложения, а более точно, как доказали Джон Хортон Конвей и Кэмерон Гордон[англ.] в 1983 году, для любого вложения   в трехмерное пространство существует два таких цикла в  , образы которых при вложении имеют нечетный коэффициент зацепления.[38] А для любого вложения графа   в трехмерное пространство существует такой гамильтонов цикл в  , образ которого при вложении имеет нетривиальный инвариант Арфа[англ.], то есть является нетривиальным узлом.[38] В 2002 году Эрика Флапан[англ.] доказала, что для любого   найдется такое  , что каждое вложение графа   в   содержит двукомпонентное зацепление, коэффициент зацепления которого равен  .[39] А кроме того, для любого   найдется такое  , что каждое вложение графа   в   содержит узел  , такой что  , где через   обозначен второй коэффициент многочлена Конвея узла  .[39]

Примеры

править

Ниже приведены полные графы с числом вершин от 1 до 12 и количества их рёбер.

K1 (0) K2 (1) K3 (3) K4 (6) K5 (10) K6 (15)
           
K7 (21) K8 (28) K9 (36) K10 (45) K11 (55) K12 (66)
           

Примечания

править
  1. Карпов Дмитрий Валерьевич, 2022, p. 17.
  2. Bang-Jensen, Gutin, 2018, p. 17.
  3. Donald E. Knuth, 2015.
  4. Mystic Rose (англ.). nrich.maths.org. Дата обращения: 22 января 2023.
  5. Gries, Schneider, 1993.
  6. Thomas L. Pirnot, 2000, p. 154.
  7. Карпов Дмитрий Валерьевич, 2022, p. 374.
  8. Joos, Kim, Kuhn, Osthus, 2019.
  9. Mehdi Hassani, 2004.
  10. Tichy, Wagner, 2005.
  11. David Callan, 2009.
  12. Frank P. Ramsey, 1930.
  13. Карпов Дмитрий Валерьевич, 2022, p. 494.
  14. Карпов Дмитрий Валерьевич, 2022, p. 424.
  15. Beineke, Wilson, 2010, p. 43.
  16. Marcus Schaefer, 2018.
  17. Blažek, Koman, 1964.
  18. Marcus Schaefer, 2018, p. 25.
  19. 1 2 Richard K. Guy, 1960.
  20. 1 2 Harary, Hill, 1963.
  21. Marcus Schaefer, 2018, 1.3 Hill and the Crossing Number of Complete Graphs, p. 25: «the first explicit statement in print seems to be in a paper by Harary and Hill».
  22. Richard K. Guy, 1972.
  23. Pan, Richter, 2007.
  24. McQuillan, Pan, Richter, 2015.
  25. Richard K. Guy, 1969.
  26. Klerk, Pasechnik, Schrijver, 2007.
  27. Brodsky, Durocher, Gethner, 2001.
  28. 1 2 Ábrego, Fernández-Merchant, Leaños, Salazar, 2012.
  29. Cetina, Hernández-Vélez, Leaños, Villalobos, 2012.
  30. 1 2 Aichholzer, 2015.
  31. Scheinerman, Wilf, 1994.
  32. Eric W. Weisstein, 2004, О задаче Сильвестра.
  33. Ábrego, Fernández-Merchant, Salazar, 2013, История исследований числа прямолинейных пересечений полных графов..
  34. Ábrego, Fernández-Merchant, Leaños, Salazar, 2010.
  35. Карпов Дмитрий Валерьевич, 2022, p. 237.
  36. Карпов Дмитрий Валерьевич, 2022, p. 308.
  37. Kainen Bernhart, 1979, pp. 320–331.
  38. 1 2 Conway, Gordon, 1983.
  39. 1 2 Flapan, 2002.

Литература

править