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

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

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

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

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

Полный график на п вершины обозначается K_п. Некоторые источники утверждают, что буква K в этом обозначении обозначает немецкое слово комплект,^[3] но немецкое название для полного графика, Vollständiger Graph, не содержит буквы K, и в других источниках утверждается, что в обозначении учитываются вклады Казимеж Куратовски к теории графов.^[4]

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

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

K_п можно разложить на п деревья Т_я такой, что Т_я имеет я вершины.^[5] Гипотеза Рингеля спрашивает, будет ли полный граф K_2п+1 можно разложить на копии любого дерева с п края.^[6] Как известно, это верно для достаточно больших п.^[7][8]

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

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

Эти числа дают максимально возможное значение Индекс Хосоя для п-вершинный граф.^[9] Количество идеальное соответствие полного графа K_п (с п даже) дается двойной факториал (п − 1)!!.^[10]

В числа пересечения вплоть до K₂₇ известны, с K₂₈ требуя либо 7233, либо 7234 пересечений. Дальнейшие значения собираются проектом «Число прямолинейных пересечений».^[11] Прямолинейные пересечения для K_п находятся

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, переместите мышь, чтобы повернуть его.^[12]

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

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

Примеры

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

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

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

Рекомендации

1. Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики» в Уилсоне, Робине; Уоткинс, Джон Дж. (Ред.), Комбинаторика: древнее и современное, Oxford University Press, стр. 7–37, ISBN  978-0191630620.
2. Мистическая роза, nrich.maths.org, получено 23 января 2012.
3. Грис, Дэвид; Шнайдер, Фред Б. (1993), Логический подход к дискретной математике, Springer-Verlag, стр. 436, г. ISBN  0387941150.
4. Пирно, Томас Л. (2000), Математика со всех сторон, Эддисон Уэсли, стр.154, ISBN  9780201308150.
5. Джус, Феликс; Ким, Джэхун; Кюн, Даниэла; Остхус, Дерик (2019-08-05). «Оптимальные упаковки деревьев ограниченной степени» (PDF). Журнал Европейского математического общества. 21 (12): 3573–3647. Дои:10.4171 / JEMS / 909. ISSN  1435-9855.
6. Рингель, Г. (1963). Теория графов и ее приложения. Материалы симпозиума Смоленице.
7. Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (08.01.2020). «Доказательство гипотезы Рингеля». arXiv:2001.02665 [math.CO ].
8. Хартнетт, Кевин. «Доказательство радуги показывает, что у графиков есть однородные части». Журнал Quanta. Получено 2020-02-20.
9. Тихи, Роберт Ф .; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов комбинаторной химии» (PDF), Журнал вычислительной биологии, 12 (7): 1004–1013, CiteSeerX  10.1.1.379.8693, Дои:10.1089 / cmb.2005.12.1004, PMID  16201918.
10. Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала, arXiv:0906.1317, Bibcode:2009arXiv0906.1317C.
11. Освин Айхольцер. «Проект прямолинейных переходных номеров». Архивировано из оригинал 30 апреля 2007 г.
12. Акос Часар, Многогранник без диагоналей. В архиве 2017-09-18 в Wayback Machine, Институт Бойяи, Сегедский университет, 1949 г.
13. Робертсон, Нил; Сеймур, П. Д.; Томас, Робин (1993), "Бесконечные вложения графов в 3-пространство", Бюллетень Американского математического общества, 28 (1): 84–89, arXiv:математика / 9301216, Дои:10.1090 / S0273-0979-1993-00335-5, МИСТЕР  1164063.
14. Конвей, Дж. Х.; Кэмерон Гордон (1983). «Узлы и связи в пространственных графах». J. Graph Th. 7 (4): 445–453. Дои:10.1002 / jgt.3190070410.

внешняя ссылка

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