Полный граф

редактировать

Полный граф
K7, полный граф с 7 вершинами
Vertices	n
Ребра	$n (n - 1) 2 {\ displaystyle \ textstyle {\ frac {n (n-1)} {2}}}$ ${\ displaystyle \ textstyle {\ frac {n (n-1)} {2 }}}$
Радиус	${0 n ≤ 1 1 иначе {\ displaystyle \ left \ {{\ begin {array} {ll} 0 n \ leq 1 \\ 1 {\ text {else}} \ end {array}} \ right.}$ $\ left \ {{\ begin {array} {ll} 0 n \ leq 1 \\ 1 {\ text {else}} \ end {array}} \ right.$
Диаметр	${0 n ≤ 1 1 иначе {\ displaystyle \ left \ {{\ begin {array} {ll} 0 n \ leq 1 \\ 1 {\ text {else}} \ end {array}} \ right.}$ $\ left \ {{\ begin {array} {ll} 0 n \ leq 1 \\ 1 {\ text {else}} \ end {array}} \ right.$
Обхват	${ ∞ n ≤ 2 3 в противном случае {\ displaystyle \ left \ {{\ begin {array} {ll} \ infty n \ leq 2 \\ 3 {\ text {else}} \ end {array}} \ right.}$ $\ left \ {{\ begin {array} {ll} \ infty n \ leq 2 \\ 3 {\ text {else}} \ end {array}} \ right.$
Автоморфизмы	n! (S n)
Хроматическое число	n
Хроматический индекс	n, если n нечетное n - 1, если n равно даже
Спектр	${∅ n = 0 {0 1} n = 1 {(n - 1) 1, - 1 n - 1} в противном случае {\ 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.}$ ${\ 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 {массив }} \ right.}$
Свойства	(n - 1) -регулярный Симметричный граф Вершинно-транзитивный Ребро- переходный Сильно регулярный Интегральный
Обозначение	Kn
Таблица графиков и параметров

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

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

Содержание

1 Свойства
2 Геометрия и топология
3 Примеры
4 См. Также
5 Ссылки
6 Внешние ссылки

Свойства

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

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

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

Knможет быть разложен на n деревьев T i так, что T i имеет i вершин. Гипотеза Рингеля спрашивает, можно ли разложить полный граф K 2n + 1 на копии любого дерева с n ребрами. Известно, что это верно для достаточно большого n.

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

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) !!.

Число пересечений от до K 27 известно, с K 28, требующих 7233 или 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 ).

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

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

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

K1по K 4 - это планарные графы. Однако каждый планарный рисунок полного графа с пятью или более вершинами должен содержать перекресток, а непланарный полный граф K 5 играет ключевую роль в характеризации планарных графов: по теореме Куратовского, граф является плоским тогда и только тогда, когда он не содержит ни K 5, ни полного двудольного графа K 3,3 в качестве подразделения, и теорема Вагнера тот же результат верен для миноров графа вместо подразделений. Как часть семьи Петерсена, K 6 играет ту же роль, что и один из запрещенных несовершеннолетних для встраивания без ссылок. Другими словами, как доказали Конвей и Гордон, каждое вложение K 6 в трехмерное пространство внутренне связано, по крайней мере, с одной парой связанных треугольников. Конвей и Гордон также показали, что любое трехмерное вложение K 7 содержит гамильтонов цикл, вложенный в пространство как нетривиальный узел.

Примеры

Полные графы на n вершинах для n от 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

См. Также

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

Ссылки

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

Викискладе есть материалы, связанные с Полными графиками.

Найдите полный график в Викисловарь, бесплатный словарь.

Weisstein, Eric W. «Complete Graph». MathWorld.