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

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

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

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

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

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

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

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

K _n можно разложить на n деревьев Ti таких, _что Ti _имеет 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]

Известны числа пересечений до К 27 _{, причем для} К ₂₈ требуется либо 7233, либо 7234 пересечения. Дополнительные значения собираются в рамках проекта «Число прямолинейных пересечений». ^[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 ₇ . ^[15] Каждый соседний многогранник в четырех или более измерениях также имеет полный скелет.

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

Примеры

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

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

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

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

1. Банг-Йенсен, Йорген; Гутин, Грегори (2018), «Основная терминология, обозначения и результаты», в Bang-Jensen, Jørgen; Гутин, Грегори (ред.), Классы ориентированных графов , Монографии Springer по математике, 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. Йоос, Феликс; Ким, Джехун; Кюн, Даниэла; Остус, Дерик (5 августа 2019 г.). «Оптимальные упаковки деревьев ограниченной степени» (PDF) . Журнал Европейского математического общества . 21 (12): 3573–3647. дои : 10.4171/JEMS/909. ISSN  1435-9855. S2CID  119315954. Архивировано (PDF) из оригинала 9 марта 2020 г. Проверено 9 марта 2020 г.
7. Рингель, Г. (1963). Теория графов и ее приложения . Материалы симпозиума Смоленице.
8. Монтгомери, Ричард; Покровский, Алексей; Судаков, Бенни (2021). «Доказательство гипотезы Рингеля». Геометрический и функциональный анализ . 31 (3): 663–720. arXiv : 2001.02665 . дои : 10.1007/s00039-021-00576-2 .
9. Хартнетт, Кевин. «Радужное доказательство показывает, что графики состоят из однородных частей». Журнал Кванта . Архивировано из оригинала 20 февраля 2020 г. Проверено 20 февраля 2020 г.
10. Хассани, М. «Циклы в графиках и нарушения». Математика. Газ. 88, 123–126, 2004.
11. Тичи, Роберт Ф.; Вагнер, Стефан (2005), «Экстремальные задачи для топологических индексов в комбинаторной химии» (PDF) , Журнал вычислительной биологии , 12 (7): 1004–1013, CiteSeerX 10.1.1.379.8693 , doi :10.1089/cmb.2005.12. 1004, PMID  16201918, заархивировано (PDF) из оригинала 21 сентября 2017 г. , получено 29 марта 2012 г. .
12. Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.
13. Освин Айххольцер. «Проект «Прямолинейный перекресток». Архивировано из оригинала 30 апреля 2007 г.
14. Акош Часар, Многогранник без диагоналей. Архивировано 18 сентября 2017 г. в Wayback Machine , Институт Бояи, Сегедский университет, 1949 г.
15. Гарднер, Мартин (1988), Путешествие во времени и другие математические недоумения, WH Freeman and Company, стр. 140, Бибкод : 1988ttom.book.....G, ISBN 0-7167-1924-Х
16. Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1993), «Бесзвенные вложения графов в трехмерное пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math/9301216 , doi : 10.1090/S0273-0979-1993- 00335-5, МР  1164063, S2CID  1110662.
17. Конвей, Дж. Х .; Кэмерон Гордон (1983). «Узлы и связи в пространственных графах». Журнал теории графов . 7 (4): 445–453. дои : 10.1002/jgt.3190070410.

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

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