Полный граф

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

Обычно полный граф с $n$ вершинами обозначается через $K_{n}$ . Некоторые источники утверждают, что буква $K$ в этом обозначении является сокращением от немецкого слова Шаблон:Lang-de,Шаблон:Sfn в переводе на Шаблон:Nobr целый», однако оригинальное название полного графа на немецком, Шаблон:Lang-de, не содержит буквы $K$ . По другой версии, такое обозначение полному графу было дано в честь Казимежа Куратовского, подчеркивая его вклад в развитие теории графов.Шаблон:Sfn

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

Полный граф с $n$ вершинами имеет $n (n - 1) / 2$ рёбер, это треугольное число.
Полный граф с $n$ вершинами является регулярным графом степени $n - 1$ .
Любой полный граф является своей максимальной кликой.
Граф $K_{n}$ является Шаблон:Нп5.
Дополнение графа $K_{n}$ – это пустой граф, то есть граф без рёбер.
Полный граф, каждое ребро которого снабжено ориентацией, называется турниром.
В полном графе не может быть независимого множества более чем из одной вершины.Шаблон:Sfn
Пусть $n \in ℕ$ , а $T_{1}, T_{2}, \dots, T_{n}$ – семейство деревьев ограниченных степеней, где для любого $i \in {1, 2, \dots n}$ число вершин дерева $T_{i}$ равно $i$ . Тогда граф $K_{n}$ можно разложить на деревья $T_{1}, T_{2}, \dots, T_{n}$ , то есть существуют попарно рёберно-непересекающиеся копии графов $T_{1}, T_{2}, \dots, T_{n}$ в графе $K_{n}$ , и каждое ребро графа $K_{n}$ принадлежит хотя бы одной из этих копий.Шаблон:Sfn
Число различных путей между двумя выделенными вершинами в полном графе $K_{n + 2}$ вычисляетсяШаблон:Sfn по формуле $w_{n + 2} = n! e_{n} = ⌊ e n! ⌋$ , где через $e$ обозначена постоянная Эйлера, и
$e_{n} = \sum_{k = 0}^{n} \frac{1}{k!} .$
Индексы Хосойи (полные числа паросочетаний) полного графа являются Шаблон:Нп5 ( $n$ -ое телефонное число – это число различных вариантов, которыми из $n$ человек можно выбрать набор пар людей, которые будут одновременно созваниваться друг с другом по телефону; в частности можно выбрать пустой набор), причем на полных графах реализуются максимально возможные значения индекса Хосойи для Шаблон:Nobr графа.Шаблон:Sfn Эти индексы образуют последовательность
1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... Шаблон:OEIS.

Число совершенных паросочетаний графа $K_{n}$ с чётным $n$ определяется с помощью двойного факториала и равняется $(n - 1)!!$ .Шаблон:Sfn
Теорема Рамсея: Для любых $c$ натуральных чисел $n_{1}, n_{2}, \dots, n_{c}$ в любой $c$ -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с $n_{i}$ вершинами для некоторого цвета $i$ . В частности, для любых $r$ и $s$ , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из $r$ вершин, либо полный белый подграф из $s$ вершин.Шаблон:Sfn
Теорема Турана: Обозначим через $ex (v, n)$ максимальное количество рёбер, которое может иметь граф с $v$ вершинами, не содержащий подграфа, изоморфного $K_{n}$ . Тогда, если $v = m (n - 1) + r$ , где $r$ — остаток от деления $v$ на $n - 1$ , то этот максимум равен $ex (v, n) = \frac{(n - 2) (v^{2} - r^{2})}{2 n - 2} + \frac{r (r - 1)}{2} .$ Среди всех графов на $v$ вершинах, не содержащих подграфа $K_{n}$ , этот максимум по количеству рёбер достигается на графе $T_{n} (v)$ , определяемом следующим образом. Пусть $T_{n} (v)$ это граф с $v$ вершинами, разобьём все вершины на $n - 1$ «почти равных» групп (то есть возьмём $r$ групп по $m + 1$ вершине и $n - 1 - r$ групп по $m$ вершин, если $v : (n - 1) = m$ с остатком $r$ ) и соединим рёбрами все пары вершин из разных групп. Таким образом получим $(n - 1)$ -дольный граф.Шаблон:Sfn
Теорема Кэли о числе деревьев: Число остовных деревьев в полном графе $K_{n}$ равно $n^{n - 2} .$ Шаблон:Sfn

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

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

Известна верхняя оценка на число пересечений полного графа, а именно $cr (K_{n}) \leq \frac{1}{4} ⌊ \frac{n}{2} ⌋ ⌊ \frac{n - 1}{2} ⌋ ⌊ \frac{n - 2}{2} ⌋ ⌊ \frac{n - 3}{2} ⌋$ . Впервые, в конце пятидесятых, вопрос о существовании такой оценки выдвинул Энтони Хилл,Шаблон:Sfn известный британский художник-абстракционист. Ему удалось разработать несколько особых методов изображения полных графов, позволивших в дальнейшем эффективно исследовать их числа пересечений. Один из таких методов известен как «рисунок на алюминиевой банке», а другой – как «изображения Харари-Хилла».Шаблон:Sfn Анализируя эти методы изображения математикам Блажеку и Коману удалось подтвердитьШаблон:Sfn оценку Хилла для всех полных графов в 1964 году. Стоит отметить, что Хилл выдвинул куда более сильную гипотезу, а именно $cr (K_{n}) = \frac{1}{4} ⌊ \frac{n}{2} ⌋ ⌊ \frac{n - 1}{2} ⌋ ⌊ \frac{n - 2}{2} ⌋ ⌊ \frac{n - 3}{2} ⌋$ . Эта гипотеза известна как гипотеза Хилла и на данный момент подтверждена только для нескольких малых $n$ .Шаблон:Sfn Гипотезу Хилла иногда называют гипотезой Гая, в честь британского математика Ричарда Гая, в чьей работеШаблон:Sfn за 1960 год содержатся прямые намеки на данный вопрос, или гипотезой Харари-Хилла, так как работаШаблон:Sfn Энтони Хилла и Фрэнка Харари за 1963 год, видимо, самая ранняя опубликованная математическая статья, содержащая точную формулировку этой гипотезы.Шаблон:Sfn Полные графы $K_{n}$ при $n \leq 4$ являются планарными, то есть их число пересечений равно 0. В 1972 году Гай показал,Шаблон:Sfn что гипотеза Хилла верна для всех $n \leq 10$ , а в 2007 году Шэнджунь Пэн и Брюс Рихтер подтвердилиШаблон:Sfn гипотезу Хилла для $n = 11, 12$ . В 2015 году Дэн Макуиллан, Шэнджунь Пэн и Брюс Рихтер выяснили,Шаблон:Sfn что $cr (K_{13})$ является нечетным числом, лежащим между 219 и 225 включительно. Вся известная на данный момент информация о точных значениях чисел пересечений полных графов представлена в таблице ниже.

Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center
$cr (G)$	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center

Кроме того, в 1969 году Гай получилШаблон:Sfn нижнюю оценку на число пересечений полного графа, а именно $cr (K_{n}) \geq \frac{1}{120} n (n - 1) (n - 2) (n - 3)$ . При этом, ещё в 1960 году он обнаружил,Шаблон:Sfn что существует предел $\lim_{n \to \infty} cr (K_{n}) / Z (n)$ , где $Z (n) = \frac{1}{4} ⌊ \frac{n}{2} ⌋ ⌊ \frac{n - 1}{2} ⌋ ⌊ \frac{n - 2}{2} ⌋ ⌊ \frac{n - 3}{2} ⌋$ , а в 2007 году Этьен де Клерк, Дмитрий Пасечник и Александр Схрейвер выяснили,Шаблон:Sfn что верна оценка

\lim_{n \to \infty} \frac{cr (K_{n})}{Z (n)} \geq 0.8594

.

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

Для $n \leq 7$ и $n = 9$ число прямолинейных пересечений графа $K_{n}$ , которое обычно обозначается через $rcr (K_{n})$ , совпадает с его обыкновенным числом пересечений. Однако, число прямолинейных пересечений графа $K_{8}$ равно $19$ , тогда как $cr (K_{8}) = 18$ .Шаблон:Sfn В 2001 году Алекс Бродский, Стефан Дуроше и Шаблон:Нп5 выяснили,Шаблон:Sfn что число прямолинейных пересечений графа $K_{10}$ равно 62, при $cr (K_{10}) = 60$ . На данный момент точные значения $rcr (K_{n})$ известны для $n \leq 27$ и $n = 30$ . Суть точного вычисления заключается в нахождении соответствующих (и совпадающих) нижних и верхних оценок. Нижние оценки для $n \leq 27$ были построеныШаблон:Sfn совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром в 2012 году, нижняя оценка для $n = 30$ построенаШаблон:Sfn совместно математиками Марио Сетина, Сесаром Эрнандес-Велесом, Хесусом Леаньосом и Кристобалем Вильялобос Гильеном в 2012 году, а все верхние оценки получены австрийским математиком Освином АйххольцеромШаблон:Sfn. Кроме того, Айххольцер опубликовалШаблон:Sfn на своем сайте суммарную информацию обо всех известных на данный момент нижних и верхних оценках на $rcr (K_{n})$ вплоть до $n = 100$ . Ниже приведена таблица с соответствующими оценками для $5 \leq n \leq 30$ .

Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center
$rcr (G)$	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center	Шаблон:Center

В 1994 году Шаблон:Нп5 и Шаблон:Нп5 обнаружилиШаблон:Sfn неожиданную связь между числом прямолинейных пересечений графа $K_{n}$ и задачей Сильвестра "о четырех точках" из вероятностной геометрии.Шаблон:Sfn Пусть $R$ — открытое множество на плоскости с конечной мерой Лебега. Обозначим через $q (R)$ вероятность того, что если в $R$ равномерно и случайно выбраны четыре точки независимо друг от друга, то их выпуклая оболочка является четырехугольником, а через $q^{*}$ – инфимум значений $q (R)$ по всем таким $R$ . Тогда верно равенство

\lim_{n \to \infty} \frac{rcr (K_{n})}{(\binom{n}{4})} = q^{*},

где $(\binom{n}{4})$ обозначает соответствующий биномиальный коэффициент. Продолжительное время уточнялисьШаблон:Sfn верхняя и нижняя оценки на константу $q^{*}$ , и на данный момент лучшая нижняяШаблон:Sfn и лучшая верхняяШаблон:Sfn оценки получены совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром, и составляют

0.379972 < \frac{277}{729} \leq q^{*} \leq \frac{83247328}{218791125} < 0.380488 .

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

Графы с $K_{1}$ по $K_{4}$ являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф $K_{5}$ и, следовательно, не удовлетворяют критерию Понтрягина — Куратовского.Шаблон:Sfn

При $n \leq 6$ граф $K_{n}$ является 1-планарным графом, но при $n \geq 7$ граф $K_{n}$ не является 1-планарным.Шаблон:Sfn

Книжная толщина графа $K_{5}$ равна $3$ . Для любых $n \geq 4$ граф $K_{n}$ имеет книжную толщину в точности $⌈ n / 2 ⌉$ .Шаблон:Sfn

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

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

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

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

Граф $K_{6}$ не имеет незацепленного вложения, а более точно, как доказали Джон Хортон Конвей и Шаблон:Нп5 в 1983 году, для любого вложения $K_{6}$ в трехмерное пространство существует два таких цикла в $K_{6}$ , образы которых при вложении имеют нечетный коэффициент зацепления.Шаблон:Sfn А для любого вложения графа $K_{7}$ в трехмерное пространство существует такой гамильтонов цикл в $K_{7}$ , образ которого при вложении имеет нетривиальный Шаблон:Нп5, то есть является нетривиальным узлом.Шаблон:Sfn В 2002 году Шаблон:Нп5 доказала, что для любого $m \in ℕ$ найдется такое $n \in ℕ$ , что каждое вложение графа $K_{n}$ в $ℝ^{3}$ содержит двукомпонентное зацепление, коэффициент зацепления которого равен $m$ .Шаблон:Sfn А кроме того, для любого $m \in ℕ$ найдется такое $r \in ℕ$ , что каждое вложение графа $K_{n}$ в $ℝ^{3}$ содержит узел $Q$ , такой что $| a_{2} (Q) | \geq m$ , где через $a_{2} (Q)$ обозначен второй коэффициент многочлена Конвея узла $Q$ .Шаблон:Sfn