Полный график

Полный график
K 7 , полный граф с 7 вершинами
Вершины	н
Края	$\textstyle {\frac {n(n-1)}{2}}$
Радиус	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.$
Диаметр	$\left\{{\begin{array}{ll}0&n\leq 1\\1&{\text{otherwise}}\end{array}}\right.$
Обхват	$\left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{otherwise}}\end{array}}\right.$
Автоморфизмы	н ! ( Сн )
Хроматическое число	н
Хроматический индекс	n, если n нечетное n - 1, если n четное
Спектр	$\left\{{\begin{array}{lll}\emptyset &n=0\\\left\{0^{1}\right\}&n=1\\\left\{(n-1)^{1},-1^{n-1}\right\}&{\text{otherwise}}\end{array}}\right.$
Характеристики	( n − 1) -регулярный Симметричный граф Вершинно-транзитивный Край-транзитивный Сильно регулярный Интеграл
Обозначения	К н
Таблица графиков и параметров

В математической области теории графов полный граф — это простой неориентированный граф , в котором каждая пара различных вершин соединена уникальным ребром . Полный орграф — это ориентированный граф , в котором каждая пара различных вершин соединена парой уникальных ребер (по одному в каждом направлении).

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

Свойства

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

K _n имеет n ( n 2 ребер ( треугольное число ) и является регулярным графом степени – 1) / n – 1 . Все полные графы являются собственными максимальными кликами . Они максимально связны , поскольку единственным разрезом вершин , который разъединяет граф, является полный набор вершин. Граф дополнений полного графа — это пустой граф .

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

K _n можно разложить на n деревьев Ti _что таких, имеет _i Ti вершин . Гипотеза Рингеля спрашивает, полный граф K _{2 n +1} можно ли разложить на копии любого дерева с n ребрами. Известно, что это справедливо для достаточно больших n .

Число всех различных путей между определенной парой вершин в K _{n +2} задано к

$w_{n+2}=n!e_{n}=\lfloor en!\rfloor ,$

где e относится к постоянной Эйлера и

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

Количество совпадений полных графов указано по номерам телефонов.

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

Эти числа дают максимально возможное значение индекса Хосоя для графа с n вершинами. Количество идеальных паросочетаний полного графа K _n (с четным n ) определяется двойным факториалом ( n – 1)!! .

К 28 требуется либо ₇₂₃₃ Известны числа пересечений до К 27, причем для , _либо 7234 пересечения. Дополнительные значения собираются в рамках проекта «Число прямолинейных пересечений». Прямолинейные числа пересечений для K _n равны

0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... (последовательность A014540 в OEIS ).

Геометрия и топология

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

Полный граф с n узлами представляет собой ребра ( n – 1 -симплекса ) . Геометрически K ₃ образует множество ребер треугольника , K 4 _— и тетраэдр т. д. Многогранник Часара — невыпуклый многогранник с топологией тора полный граф K ₇ — имеет в качестве скелета . Каждый соседний многогранник в четырех и более измерениях также имеет полный скелет.

K1 _– являются K4 _Все плоскими графами . Однако каждый планарный рисунок полного графа с пятью и более вершинами должен содержать пересечение, а непланарный полный граф играет _К5 ключевую роль в характеристиках планарных графов: по теореме Куратовского граф планарен тогда и только тогда, когда он не содержит ни K ₅ , ни полного двудольного графа K _3,3 в качестве подразделения, и по теореме Вагнера тот же результат справедлив для миноров графа вместо подразделений. Как часть семейства Петерсенов , K6 _для играет роль одного из запрещенных второстепенных файлов бессвязного встраивания . Другими словами, и как Конвей и Гордон Доказано, что каждое вложение K ₆ в трехмерное пространство внутренне зацеплено, по крайней мере, с одной парой зацепленных треугольников. Конвей и Гордон также показали, что любое трехмерное вложение K ₇ содержит гамильтонов цикл , вложенный в пространство как нетривиальный узел .

Примеры

Полные графики на $n$ вершины, для $n$ от 1 до 12 показаны ниже вместе с количеством ребер:

К 1 : 0	К 2 : 1	К 3 : 3	К 4 : 6
К 5 : 10	К 6:15 ​	К7 21 :	К 8:28 ​
К9 : 36	К 10:45 ​	К 11:55 ​	К 12:66 ​

См. также

• Полностью подключенная сеть в компьютерной сети
• Полный двудольный граф (или биклика ), специальный двудольный граф , в котором каждая вершина на одной стороне двудольного деления соединена с каждой вершиной на другой стороне.
• Симплекс , который идентичен полному графу $n+1$ вершины, где $n$ - размерность симплекса.

Внешние ссылки

• Вайсштейн, Эрик В. «Полный граф» . Математический мир .