Полный граф

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

Полный граф
K7, полный граф с 7 вершинами
Вершин	n
Рёбер	$\frac{n(n-<!--\; -\; -->1)}{2}$${\frac {n(n-1)}{2}}$
Диаметр	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{иначе}}\end{array}}\right.$
Обхват	$\left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{иначе}}\end{array}}\right.$
Автоморфизмы	n! (Sn)
Хроматическое число	n
Хроматический индекс	n если n - нечётное, иначе n − 1
Спектр	$\left\{{\begin{array}{lll}\emptyset &n=0\\\left\{0^{1}\right\}&n=1\\\left\{(n-1)^{1},-1^{n-1}\right\}&{\text{иначе}}\end{array}}\right.$
Свойства	(n − 1)-регулярный граф Симметричный граф Вершинно-транзитивный граф Рёберно-транзитивный граф Сильно регулярный граф Целый граф Гамильтонов граф
Обозначение	Kn
Медиафайлы на Викискладе

Полный граф $K_9$$K_{9}$ на рисунке из труда Ars Magna Раймунда Луллия.

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

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

• Полный граф с $n$$n$  вершинами имеет $n(n-<!--\; -\; -->1)/2$$n(n-1)/2$  рёбер, это треугольное число.

• Полный граф с $n$$n$  вершинами является регулярным графом степени $n-<!--\; -\; -->1$$n-1$ .

• Любой полный граф является своей максимальной кликой.

• Граф $K_n$$K_n$  является $(n-<!--\; -\; -->1)$$(n-1)$ -связным.

• Дополнение графа $K_n$$K_n$  – это пустой граф, то есть граф без рёбер.

• Полный граф, каждое ребро которого снабжено ориентацией, называется турниром.

• В полном графе не может быть независимого множества более чем из одной вершины.

• Пусть $n\in <!--\; \in \; -->\mathbb{N}$$n\in \mathbb {N}$ , а $T_1,T_2,\dots <!--\; \dots \; -->,T_n$$\,T_{1},T_{2},\dots ,T_{n}$  – семейство деревьев ограниченных степеней, где для любого $i\in <!--\; \in \; -->\{1,2,\dots <!--\; \dots \; -->n\}$$i\in \{1,2,\dots n\}$  число вершин дерева $T_i$$T_{i}$  равно $i$$i$ . Тогда граф $K_n$$K_n$  можно разложить на деревья $T_1,T_2,\dots <!--\; \dots \; -->,T_n$$\,T_{1},T_{2},\dots ,T_{n}$ , то есть существуют попарно рёберно-непересекающиеся копии графов $T_1,T_2,\dots <!--\; \dots \; -->,T_n$$\,T_{1},T_{2},\dots ,T_{n}$  в графе $K_n$$K_n$ , и каждое ребро графа $K_n$$K_n$  принадлежит хотя бы одной из этих копий.

• Число различных путей между двумя выделенными вершинами в полном графе $K_{n+2}$$K_{n+2}$  вычисляется по формуле $w_{n+2}=n!e_n=\lfloor <!--\; \lfloor \; -->en!\rfloor <!--\; \rfloor \; -->$$w_{n+2}=n!e_{n}=\lfloor en!\rfloor$ , где через $e$$e$  обозначена постоянная Эйлера, и

  $e_n=\underset{k=0}{\overset{n}{\sum <!--\; \sum \; -->}}\frac{1}{k!}.$$e_{n}=\sum _{k=0}^{n}{\frac {1}{k!}}.$ 

• Индексы Хосойи (полные числа паросочетаний) полного графа являются телефонными числами ($n$$n$ -ое телефонное число – это число различных вариантов, которыми из $n$$n$  человек можно выбрать набор пар людей, которые будут одновременно созваниваться друг с другом по телефону; в частности можно выбрать пустой набор), причем на полных графах реализуются максимально возможные значения индекса Хосойи для $n$$n$ -вершинного графа. Эти индексы образуют последовательность

  1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... последовательность A000085 в OEIS.

• Число совершенных паросочетаний графа $K_n$$K_n$  с чётным $n$$n$  определяется с помощью двойного факториала и равняется $(n-<!--\; -\; -->1)!!$$(n-1)!!$ .

• Теорема Рамсея: Для любых $c$$c$  натуральных чисел $n_1,n_2,\dots <!--\; \dots \; -->,n_c$$n_{1},n_{2},\dots ,n_{c}$  в любой $c$$c$ -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с $n_i$$n_{i}$  вершинами для некоторого цвета $i$$i$ . В частности, для любых $r$$r$  и $s$$s$ , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из $r$$r$  вершин, либо полный белый подграф из $s$$s$  вершин.

• Теорема Турана: Обозначим через $\text{ex}(v,n)$${\textrm {ex}}(v,n)$  максимальное количество рёбер, которое может иметь граф с $v$$v$  вершинами, не содержащий подграфа, изоморфного $K_n$$K_n$ . Тогда, если $v=m(n-<!--\; -\; -->1)+r$$v=m(n-1)+r$ , где $r$$r$  — остаток от деления $v$$v$  на $n-<!--\; -\; -->1$$n-1$ , то этот максимум равен $\text{ex}(v,n)=\frac{(n-<!--\; -\; -->2)(v^2-<!--\; -\; -->r^2)}{2n-<!--\; -\; -->2}+\frac{r(r-<!--\; -\; -->1)}{2}.$${\textrm {ex}}(v,n)={\frac {(n-2)(v^{2}-r^{2})}{2n-2}}+{\frac {r(r-1)}{2}}.$  Среди всех графов на $v$$v$  вершинах, не содержащих подграфа $K_n$$K_n$ , этот максимум по количеству рёбер достигается на графе $T_n(v)$$T_{n}(v)$ , определяемом следующим образом. Пусть $T_n(v)$$T_{n}(v)$  это граф с $v$$v$  вершинами, разобьём все вершины на $n-<!--\; -\; -->1$$n-1$  «почти равных» групп (то есть возьмём $r$$r$  групп по $m+1$$m+1$  вершине и $n-<!--\; -\; -->1-<!--\; -\; -->r$$n-1-r$  групп по $m$$m$  вершин, если $v:(n-<!--\; -\; -->1)=m$$v:(n-1)=m$  с остатком $r$$r$ ) и соединим рёбрами все пары вершин из разных групп. Таким образом получим $(n-<!--\; -\; -->1)$$(n-1)$ -дольный граф.

• Теорема Кэли о числе деревьев: Число остовных деревьев в полном графе $K_n$$K_n$  равно $n^{n-<!--\; -\; -->2}.$$n^{n-2}.$ 

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

Число пересеченийПравить

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

$G$$G$	$K_5$$K_{5}$	$K_6$$K_{6}$	$K_7$$K_{7}$	$K_8$$K_{8}$	$K_9$$K_{9}$	$K_{10}$$K_{10}$	$K_{11}$$K_{11}$	$K_{12}$$K_{12}$	$K_{13}$$K_{13}$
$\text{cr}(G)$${\textrm {cr}}(G)$	$1$$1$	$3$$3$	$9$$9$	$18$$18$	$36$$36$	$60$$60$	$100$$100$	$150$$150$	$219,221,223$$219,221,223$  или $225$$225$

Кроме того, в 1969 году Гай получил нижнюю оценку на число пересечений полного графа, а именно $\text{cr}(K_n)\ge <!--\; \ge \; -->\frac{1}{120}n(n-<!--\; -\; -->1)(n-<!--\; -\; -->2)(n-<!--\; -\; -->3)$${\textrm {cr}}(K_{n})\geq {\tfrac {1}{120}}n(n-1)(n-2)(n-3)$ . При этом, ещё в 1960 году он обнаружил, что существует предел $\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\text{cr}(K_n)/Z(n)$$\lim _{n\to \infty }{{\textrm {cr}}(K_{n})/Z(n)}$ , где $Z(n)=\frac{1}{4}\lfloor \frac{n}{2}\rfloor \lfloor \frac{n-<!--\; -\; -->1}{2}\rfloor \lfloor \frac{n-<!--\; -\; -->2}{2}\rfloor \lfloor \frac{n-<!--\; -\; -->3}{2}\rfloor$$Z(n)={\tfrac {1}{4}}\left\lfloor {\tfrac {n}{2}}\right\rfloor \left\lfloor {\tfrac {n-1}{2}}\right\rfloor \left\lfloor {\tfrac {n-2}{2}}\right\rfloor \left\lfloor {\tfrac {n-3}{2}}\right\rfloor$ , а в 2007 году Этьен де Клерк, Дмитрий Пасечник и Александр Схрейвер выяснили, что верна оценка

$\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{\text{cr}(K_n)}{Z(n)}\ge <!--\; \ge \; -->0.8594$$\lim _{n\to \infty }{\frac {{\textrm {cr}}(K_{n})}{Z(n)}}\geq 0.8594$ .

Число прямолинейных пересеченийПравить

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

$G$$G$	$K_5$$K_{5}$	$K_6$$K_{6}$	$K_7$$K_{7}$	$K_8$$K_{8}$	$K_9$$K_{9}$	$K_{10}$$K_{10}$	$K_{11}$$K_{11}$	$K_{12}$$K_{12}$	$K_{13}$$K_{13}$	$K_{14}$$K_{14}$	$K_{15}$$K_{15}$	$K_{16}$$K_{16}$	$K_{17}$$K_{17}$	$K_{18}$$K_{18}$	$K_{19}$$K_{19}$	$K_{20}$$K_{20}$	$K_{21}$$K_{21}$	$K_{22}$$K_{22}$	$K_{23}$$K_{23}$	$K_{24}$$K_{24}$	$K_{25}$$K_{25}$	$K_{26}$$K_{26}$	$K_{27}$$K_{27}$	$K_{28}$$K_{28}$	$K_{29}$$K_{29}$	$K_{30}$$K_{30}$
$\text{rcr}(G)$${\textrm {rcr}}(G)$	$1$$1$	$3$$3$	$9$$9$	$19$$19$	$36$$36$	$62$$62$	$102$$102$	$153$$153$	$229$$229$	$324$$324$	$447$$447$	$603$$603$	$798$$798$	$1029$$1029$	$1318$$1318$	$1657$$1657$	$2055$$2055$	$2528$$2528$	$3077$$3077$	$3699$$3699$	$4430$$4430$	$5250$$5250$	$6180$$6180$	$7233$$7233$  или $7234$$7234$	$8421$$8421$ , $8422$$8422$  или $8423$$8423$	$9726$$9726$

В 1994 году Эдвард Р. Шайнерман и Герберт С. Уилф обнаружили неожиданную связь между числом прямолинейных пересечений графа $K_n$$K_n$  и задачей Сильвестра "о четырех точках" из вероятностной геометрии. Пусть $R$$R$  — открытое множество на плоскости с конечной мерой Лебега. Обозначим через $\text{q}(R)$${\textrm {q}}(R)$  вероятность того, что если в $R$$R$  равномерно и случайно выбраны четыре точки независимо друг от друга, то их выпуклая оболочка является четырехугольником, а через ${\text{q}}^{\ast <!--\; \ast \; -->}$${\textrm {q}}^{*}$  – инфимум значений $\text{q}(R)$${\textrm {q}}(R)$  по всем таким $R$$R$ . Тогда верно равенство

$\underset{n\to <!--\; \to \; -->\mathrm{\infty <!--\; \infty \; -->}}{lim}\frac{\text{rcr}(K_n)}{(\genfrac{}{}{0ex}{}{n}{4})}={\text{q}}^{\ast <!--\; \ast \; -->},$$\lim _{n\to \infty }{\frac {{\textrm {rcr}}(K_{n})}{n \choose 4}}={\textrm {q}}^{*},$ 

где $(\genfrac{}{}{0ex}{}{n}{4})$${n \choose 4}$  обозначает соответствующий биномиальный коэффициент. Продолжительное время уточнялись верхняя и нижняя оценки на константу ${\text{q}}^{\ast <!--\; \ast \; -->}$${\textrm {q}}^{*}$ , и на данный момент лучшая нижняя и лучшая верхняя оценки получены совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром, и составляют

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

ПланарностьПравить

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

При $n\le <!--\; \le \; -->6$$n\leq 6$  граф $K_n$$K_n$  является 1-планарным графом, но при $n\ge <!--\; \ge \; -->7$$n\geq 7$  граф $K_n$$K_n$  не является 1-планарным.

Симплексы и многогранникиПравить

 

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

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

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

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

Граф $K_6$$K_{6}$  не имеет незацепленного вложения, а более точно, как доказали Джон Хортон Конвей и Кэмерон Гордон, для любого вложения $K_6$$K_{6}$  в трехмерное пространство существует два таких цикла в $K_6$$K_{6}$ , образы которых при вложении имеют нечетный коэффициент зацепления. А для любого вложения графа $K_7$$K_{7}$  в трехмерное пространство существует такой гамильтонов цикл в $K_7$$K_{7}$ , образ которого при вложении имеет нетривиальный инвариант Арфа, то есть является нетривиальным узлом.

ПримерыПравить

Ниже приведены полные графы с числом вершин от 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