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

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

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

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

Характеристики

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

${\ displaystyle K_ {n}}$имеет ребра (а треугольное число ), и является регулярным графом по степени . Все полные графы - это их собственные максимальные клики . Они максимально связаны, так как единственная вершина, отсекающая граф, - это полный набор вершин. Комплемента график полного графа является пустым графом . ${\ Displaystyle п (п-1) / 2}$ ${\ displaystyle n-1}$

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

${\ displaystyle K_ {n}}$можно разложить на деревья , имеющие вершины. Гипотеза Рингеля спрашивает, можно ли разложить полный граф на копии любого дерева с ребрами. Как известно, это верно для достаточно больших . ${\ displaystyle n}$${\ displaystyle T_ {i}}$${\ displaystyle T_ {i}}$${\ displaystyle i}$${\ displaystyle K_ {2n + 1}}$${\ displaystyle n}$${\ displaystyle n}$

Количество всех различных путей между определенной парой вершин в определяется выражением ${\ displaystyle K_ {n + 2}}$

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

где относится к постоянной Эйлера , а ${\ displaystyle e}$

${\ displaystyle 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 ).

Эти числа дают максимально возможное значение индекса Хосоя для -вершинного графа. Количество точных совпадений полного графа (с четным) дается двойным факториалом . ${\ displaystyle n}$${\ displaystyle K_ {n}}$${\ displaystyle n}$ ${\ Displaystyle (п-1) !!}$

Номера переходов до известны, при этом требуется либо 7233, либо 7234 перехода. Дальнейшие значения собираются проектом «Число прямолинейных пересечений». Прямолинейный Crossing номер для АРЯ ${\ displaystyle K_ {27}}$${\ displaystyle K_ {28}}$${\ displaystyle 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 переместите мышь, чтобы повернуть его.

Полный граф с узлами представляет края с - симплекс . Геометрически K ₃ образует множество ребер треугольника , K ₄ - тетраэдр и т. Д. Многогранник Часара , невыпуклый многогранник с топологией тора , имеет полный граф K _{7 в} качестве скелета . Каждый соседний многогранник в четырех или более измерениях также имеет полный скелет. ${\ displaystyle n}$${\ Displaystyle (п-1)}$

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

Примеры

Полные графы на вершинах от 1 до 12 показаны ниже вместе с номерами ребер: ${\ displaystyle n}$${\ displaystyle n}$

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

Смотрите также

• Полностью подключенная сеть в компьютерных сетях
• Полный двудольный граф (или биклика ), специальный двудольный граф, в котором каждая вершина на одной стороне двудольного графа соединена с каждой вершиной на другой стороне

использованная литература

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

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