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

Полный график
$K 7$ , полный граф с 7 вершинами
Вершины	$п$
Края	${\ Displaystyle \ textstyle {\ гидроразрыва {п (п-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.$
Автоморфизмы	$п! (S n)$
Хроматическое число	$п$
Хроматический индекс	$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)$ -регулярный Симметричный граф Вершинно-транзитивный Edge-транзитивный Сильно регулярный интеграл
Обозначение	$K n$
Таблица графиков и параметров

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

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

Свойства [ править ]

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

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

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

K _n можно разложить на $n$ деревьев T _i, таких что T _i имеет $i$ вершин. ^[5] Гипотеза Рингеля спрашивает, можно ли разложить полный граф K _{2 n +1} на копии любого дерева с $n$ ребрами. ^[6] Это, как известно, верно для достаточно больших $n$ . ^[7]^[8]

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

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

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

Номера переходов до K ₂₇ известны, при этом K ₂₈ требует либо 7233, либо 7234 переходов. Дальнейшие значения собираются проектом «Число прямолинейных пересечений». ^[11] Прямолинейные числа пересечений для 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 переместите мышь, чтобы повернуть его. ^[12]

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

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

Примеры [ править ]

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

$К 1 : 0$	$К 2 : 1$	$К 3 : 3$	$К 4 : 6$

$К 5 : 10$	$К 6 : 15$	$К 7 : 21$	$K 8 : 28$

$К 9 : 36$	$К 10 : 45$	$K 11 : 55$	$К 12 : 66$

См. Также [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

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

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

[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. DOI : 10.4171 / JEMS / 909 . ISSN 1435-9855 .

[6] Рингель, Г. (1963). Теория графов и ее приложения . Материалы симпозиума Смоленице.

[7] Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (08.01.2020). «Доказательство гипотезы Рингеля». arXiv : 2001.02665 [ math.CO ].

[8] Хартнетт, Кевин. «Доказательство радуги показывает, что у графиков есть однородные части» . Журнал Quanta . Проверено 20 февраля 2020 .

[9] Тихи, Роберт Ф .; Вагнер, Стефан (2005), "Экстремальные задачи для топологических индексов в комбинаторной химии" (PDF) , Журнал вычислительной биологии , 12 (7): 1004-1013, CiteSeerX 10.1.1.379.8693 , DOI : 10,1089 / cmb.2005.12. 1004 , PMID 16201918 .

[10] Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.

[11] Освин Aichholzer. «Проект прямолинейного перекрестка» . Архивировано из оригинала на 2007-04-30.

[12] Акос Часар, Многогранник без диагоналей. Архивировано 18 сентября 2017 года в Wayback Machine , Институт Бойяи, Сегедский университет, 1949 год.

[13] Робертсон, Нил ; Сеймур, PD ; Томас, Робин (1993), "Бесконечные вложения графов в 3-пространство", Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math / 9301216 , doi : 10.1090 / S0273-0979-1993- 00335-5 , Руководство по ремонту 1164063 .

[14] Конвей, JH ; Кэмерон Гордон (1983). «Узлы и связи в пространственных графах». J. Graph Th . 7 (4): 445–453. DOI : 10.1002 / jgt.3190070410 .

[1]