Полный граф

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

Полный граф
K7, полный граф с 7 вершинами
Вершин	n
Рёбер	${\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}$ на рисунке из труда Ars Magna Раймунда Луллия.

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

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

• Полный граф с $n$ вершинами имеет $n(n-1)/2$ рёбер, это треугольное число.
• Полный граф с $n$ вершинами является регулярным графом степени $n-1$.
• Любой полный граф является своей максимальной кликой.
• Граф $K_{n}$ является $(n-1)$-связным.
• Дополнение графа $K_{n}$ – это пустой граф, то есть граф без рёбер.
• Полный граф, каждое ребро которого снабжено ориентацией, называется турниром.
• В полном графе не может быть независимого множества более чем из одной вершины.
• Пусть $n\in \mathbb {N}$, а $\,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}$ принадлежит хотя бы одной из этих копий.
• Число различных путей между двумя выделенными вершинами в полном графе $K_{n+2}$ вычисляется по формуле $w_{n+2}=n!e_{n}=\lfloor en!\rfloor$, где через $e$ обозначена постоянная Эйлера, и

  $e_{n}=\sum _{k=0}^{n}{\frac {1}{k!}}.$

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

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

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

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

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

Известна верхняя оценка на число пересечений полного графа, а именно ${\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 году. Стоит отметить, что Хилл выдвинул куда более сильную гипотезу, а именно ${\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$. Гипотезу Хилла иногда называют гипотезой Гая, в честь британского математика Ричарда Гая, в чьей работе за 1960 год содержатся прямые намеки на данный вопрос, или гипотезой Харари-Хилла, так как работа Энтони Хилла и Фрэнка Харари за 1963 год, видимо, самая ранняя опубликованная математическая статья, содержащая точную формулировку этой гипотезы. Полные графы $K_{n}$ при $n\leq 4$ являются планарными, то есть их число пересечений равно 0. В 1972 году Гай показал, что гипотеза Хилла верна для всех $n\leq 10$, а в 2007 году Шэнджунь Пэн и Брюс Рихтер подтвердили гипотезу Хилла для $n=11,12$. В 2015 году Дэн Макуиллан, Шэнджунь Пэн и Брюс Рихтер выяснили, что ${\textrm {cr}}(K_{13})$ является нечетным числом, лежащим между 219 и 225 включительно. Вся известная на данный момент информация о точных значениях чисел пересечений полных графов представлена в таблице ниже.

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

Кроме того, в 1969 году Гай получил нижнюю оценку на число пересечений полного графа, а именно ${\textrm {cr}}(K_{n})\geq {\tfrac {1}{120}}n(n-1)(n-2)(n-3)$. При этом, ещё в 1960 году он обнаружил, что существует предел $\lim _{n\to \infty }{{\textrm {cr}}(K_{n})/Z(n)}$, где $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 году Этьен де Клерк, Дмитрий Пасечник и Александр Схрейвер выяснили, что верна оценка

$\lim _{n\to \infty }{\frac {{\textrm {cr}}(K_{n})}{Z(n)}}\geq 0.8594$.

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

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

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

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

$\lim _{n\to \infty }{\frac {{\textrm {rcr}}(K_{n})}{n \choose 4}}={\textrm {q}}^{*},$

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

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

Книжное вложение с тремя страницами для графа $K_{5}$

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

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

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

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

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

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

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

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

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

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

Примеры

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

Литература

• Карпов Д. В. Теория графов (рус.) — М.: МЦНМО, 2022. — 560 с. — ISBN 978-5-4439-1690-3.
• Ábrego B. M., Fernández-Merchant S., Salazar G. The rectilinear crossing number of $K_{n}$: Closing in (or Are We?) (англ.) // Thirty essays on geometric graph theory / János Pach|en. — N. Y.: Springer, 2013. — P. 5-18. — doi:10.1007/978-1-4614-0110-0_2.
• Ábrego B. M., Fernández-Merchant S., Leaños J., Salazar G. 3-symmetric and 3-decomposable geometric drawings of $K_{n}$ (англ.) // Discrete Applied Mathematics. — 2010. — Vol. 158, iss. 12. — P. 1240-1258. — doi:10.1016/j.dam.2009.09.020.
• Ábrego B. M., Fernández-Merchant S., Leaños J., Salazar G. On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of $K_{n}$ (англ.) // Discrete & Computational Geometry. — 2012. — Vol. 48, iss. 1. — P. 192-215. — doi:10.1007/s00454-012-9403-y.
• Aichholzer O. On the Rectilinear Crossing Number (англ.) (26 мая 2015). Дата обращения: 22 января 2023.
• Bang-Jensen J., Gutin G.. Classes of Directed Graphs (англ.) — Springer International Publishing, 2018. — 560 p. — (Springer Monographs in Mathematics). — doi:10.1007/978-3-319-71840-8_1.
• Beineke L. W., Wilson R.. The early history of the brick factory problem (англ.) // The Mathematical Intelligencer. — 2010. — Vol. 32, iss. 2. — P. 41-48. — doi:10.1007/s00283-009-9120-4.
• Bernhart F. R., Kainen P. C.. The book thickness of a graph // Journal of Combinatorial Theory. — 1979. — Т. 27, вып. 3. — С. 320–331. — doi:10.1016/0095-8956(79)90021-2.
• Blažek J., Koman M. A minimal problem concerning complete plane graphs (англ.) // Miroslav Fiedler Theory of graphs and its applications. — Czech Academy of Sciences, 1964. — P. 113-117.
• Brodsky A., Durocher S., Gethner E.. The rectilinear crossing number of $K_{10}$ is 62 (англ.) // The Electronic Journal of Combinatorics. — 2001. — Vol. 8, iss. 1. — P. 1-30.
• Callan D. A combinatorial survey of identities for the double factorial (англ.). — 2009. — . — arXiv:0906.1317.
• Cetina M., Hernández-Vélez C., Leaños J., Guillén C. V. Point sets that minimize (≤k)-edges, 3-decomposable drawings, and the rectilinear crossing number of $K_{30}$ (англ.) // Discrete Mathematics. — 2012. — Vol. 311, iss. 16. — P. 1646–1657. — doi:10.1016/j.disc.2011.03.030.
• Conway J. H., Gordon C. McA. Knots and links in spatial graphs (англ.) // Journal of Graph Theory. — 1983. — Vol. 7, no. 4. — P. 445-453. — doi:10.1002/jgt.3190070410.
• Erica Flapan. Intrinsic knotting and linking of complete graphs (англ.) // Algebraic & Geometric Topology. — 2002. — Vol. 2, no. 1. — P. 371-380. — doi:10.2140/agt.2002.2.371.
• Gries D., Schneider F. B. A Logical Approach to Discrete Math (англ.) — B.: Springer, 1993. — 436 p. — ISBN 978-0387941158.
• Guy R. K. A combinatorial problem (англ.) // NABLA (Bulletin of the Malaysian Mathematical Sciences Society). — 1960. — Vol. 7. — P. 68-72.
• Guy R. K. The decline and fall of Zarankiewicz’s theorem (англ.) // Frank Harary Proof Techniques in Graph Theory. — N. Y.: Academic Press, 1969. — P. 63–69.
• Guy R. K. Crossing numbers of graphs (англ.) // Graph Theory and Applications. — Berlin, Heidelberg: Springer, 1972. — P. 111-124.
• Harary F., Hill A. On the number of crossings in a complete graph (англ.) // Proceedings of the Edinburgh Mathematical Society. — Edinburgh, 1963. — Vol. 13, iss. 4. — P. 333-338.
• Hassani M. Cycles in graphs and derangements (англ.) // The Mathematical Gazette. — 2004. — Vol. 88, iss. 511. — P. 123-126. — doi:10.1017/S0025557200174443.
• Joos F., Kim J., Kuhn D., Osthus D. Optimal packings of bounded degree trees (англ.) // Journal of the European Mathematical Society. — 2019. — 8 May (vol. 21, iss. 12). — P. 3573-3647. — ISSN 1435-9855. — doi:10.4171/JEMS/909.
• de Klerk E., Pasechnik D. V., Schrijver A. Reduction of symmetric semidefinite programs using the regular ∗-representation (англ.) // Mathematical Programming. — 2007. — Vol. 109, iss. 2-3, Ser. B. — P. 613-624. — doi:10.1007/s10107-006-0039-7.
• Knuth D. E. Two thousand years of combinatorics // Combinatorics: Ancient & Modern (англ.) / Robin Wilson, John J. Watkins. — Oxf.: Oxford University Press, 2015. — P. 7–37. — 392 p. — ISBN 978-0191630620.
• McQuillan D., Pan S., Richter R. B. On the crossing number of $K_{13}$ (англ.) // Journal of Combinatorial Theory, Series B. — 2015. — Vol. 115. — P. 224–235. — doi:10.1016/j.jctb.2015.06.002.
• Pirnot T. L. Mathematics All Around (англ.) — Boston: Addison Wesley, 2000. — 814 p. — ISBN 978-0201308150.
• Pan S., Richter B. R. The crossing number of $K_{11}$ is 100 (англ.) // Journal of Graph Theory. — 2007. — Vol. 56, iss. 2. — P. 128-134. — doi:10.1002/jgt.20249.
• Ramsey F. P. On a problem of formal logic (англ.) // Proceedings of the London Mathematical Society. — L., 1930. — Vol. 30. — P. 264—286. — doi:10.1112/plms/s2-30.1.264.
• Schaefer M. Crossing numbers of graphs (англ.) — Boca Raton: CRC Press, 2018. — 376 p. — doi:10.1201/9781315152394.
• Scheinerman E. R., Wilf H. S.. The rectilinear crossing number of a complete graph and Sylvester's “four point problem” of geometric probability (англ.) // The American mathematical monthly. — 1994. — Vol. 101, iss. 10. — P. 939-943. — doi:10.2307/2975158.
• Tichy R. F., Wagner S. Extremal problems for topological indices in combinatorial chemistry (англ.) // Journal of Computational Biology. — 2005. — Vol. 12, iss. 7. — P. 1004–1013. — doi:10.1089/cmb.2005.12.1004. — PMID 16201918.
• Weisstein E. W. Sylvester's Four-Point Problem (англ.) (2004). Дата обращения: 24 января 2023.