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

Граф, в котором каждые две вершины смежны

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

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

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

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

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

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

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

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

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

где 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 ).

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

Известны числа пересечений до K 27, при этом для K 28 требуется либо ₇₂₃₃ , _либо 7234 пересечений. Дальнейшие значения собираются в рамках проекта Rectilinear Crossing Number. ^[13] Числа прямолинейных пересечений для 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 переместите мышь, чтобы повернуть его. ^[14]

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

Графы от K ₁ до K ₄ являются планарными графами . Однако каждое планарное изображение полного графа с пятью или более вершинами должно содержать пересечение, а непланарный полный граф K ₅ играет ключевую роль в характеристиках планарных графов: по теореме Куратовского граф является планарным тогда и только тогда, когда он не содержит ни K ₅ , ни полного двудольного графа K _3,3 в качестве подразделения, а по теореме Вагнера тот же результат справедлив для миноров графа вместо подразделений. Как часть семейства Петерсена , K ₆ играет аналогичную роль одного из запрещенных миноров для вложения без зацеплений . ^[16] Другими словами, и как доказали Конвей и Гордон ^[17] , каждое вложение K ₆ в трехмерное пространство внутренне связано, по крайней мере с одной парой связанных треугольников. _{Конвей и Гордон также показали ,} что любое трехмерное вложение K7 содержит гамильтонов цикл , который вложен в пространство как нетривиальный узел .

Примеры

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

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

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

Ссылки

1. Банг-Йенсен, Йорген; Гутин, Грегори (2018), «Основная терминология, обозначения и результаты», в Банг-Йенсен, Йорген; Гутин, Грегори (ред.), Классы направленных графов , Springer Monographs in Mathematics, Springer International Publishing, стр. 1–34, doi : 10.1007/978-3-319-71840-8_1; см. стр. 17
2. Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики», в Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: древняя и современная , Oxford University Press, стр. 7–37, ISBN 978-0191630620.
3. Mystic Rose, nrich.maths.org , получено 23 января 2012 г..
4. Грайс, Дэвид ; Шнайдер, Фред Б. (1993), Логический подход к дискретной математике, Springer-Verlag, стр. 436, ISBN 0387941150.
5. Пирнот, Томас Л. (2000), Математика во всем, Эддисон Уэсли, стр. 154, ISBN 9780201308150.
6. Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (2019-08-05). "Optimal packings of bounded degree trees" (PDF) . Journal of the European Mathematical Society . 21 (12): 3573–3647. doi :10.4171/JEMS/909. ISSN  1435-9855. S2CID  119315954. Архивировано (PDF) из оригинала 2020-03-09 . Получено 2020-03-09 .
7. Рингель, Г. (1963). Теория графов и ее приложения . Труды симпозиума в Смоленице.
8. Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (2021). «Доказательство гипотезы Рингеля». Геометрический и функциональный анализ . 31 (3): 663–720. arXiv : 2001.02665 . doi : 10.1007/s00039-021-00576-2 .
9. Хартнетт, Кевин. «Rainbow Proof Shows Graphs Have Uniform Parts». Журнал Quanta . Архивировано из оригинала 20.02.2020 . Получено 20.02.2020 .
10. Хассани, М. «Циклы в графах и расстройства». Math. Gaz. 88, 123–126, 2004.
11. Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indexes in combinatorial chemistry" (PDF) , Journal of Computational Biology , 12 (7): 1004–1013, CiteSeerX 10.1.1.379.8693 , doi :10.1089/cmb.2005.12.1004, PMID  16201918, заархивировано (PDF) из оригинала 21.09.2017 , извлечено 29.03.2012 .
12. Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.
13. Освин Айххольцер. "Проект прямолинейного пересечения чисел". Архивировано из оригинала 2007-04-30.
14. Акош Часар, Многогранник без диагоналей. Архивировано 18 сентября 2017 г. в Wayback Machine , Институт Боляи, Сегедский университет, 1949 г.
15. Гарднер, Мартин (1988), Путешествие во времени и другие математические недоумения, WH Freeman and Company, стр. 140, Bibcode : 1988ttom.book.....G, ISBN 0-7167-1924-X
16. Робертсон, Нил ; Сеймур, П. Д.; Томас , Робин (1993), «Безсвязные вложения графов в 3-пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math/9301216 , doi :10.1090/S0273-0979-1993-00335-5, MR  1164063, S2CID  1110662.
17. Конвей, Дж. Х .; Кэмерон Гордон (1983). «Узлы и связи в пространственных графах». Журнал теории графов . 7 (4): 445–453. doi :10.1002/jgt.3190070410.

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

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