Полный граф на n вершинах обозначается K n . Некоторые источники утверждают, что буква K в этом обозначении обозначает немецкое слово komplett , [4] но немецкое название полного графа, vollständiger Graph , не содержит буквы K , а другие источники утверждают, что в обозначении учитываются вклады Казимеж Куратовский к теории графов. [5]
K n можно разложить на n деревьев Ti таких, что Ti имеет i вершин . [6] Гипотеза Рингеля спрашивает, можно ли разложить полный граф K 2 n +1 на копии любого дерева с n ребрами. [7] Известно, что это справедливо для достаточно больших n . [8] [9]
Число всех различных путей между конкретной парой вершин в K n +2 определяется [10] выражением
Эти числа дают максимально возможное значение индекса Хосоя для графа с n вершинами. [11] Число совершенных паросочетаний полного графа K n (с четным n ) определяется двойным факториалом ( n – 1)!! . [12]
Известны числа пересечений до К 27 , причем для К 28 требуется либо 7233, либо 7234 пересечения. Дополнительные значения собираются в рамках проекта «Число прямолинейных пересечений». [13] Прямолинейные числа пересечения для K n равны
Полный граф с n узлами представляет собой ребра ( n – 1) -симплекса . Геометрически K 3 образует множество ребер треугольника , K 4 — тетраэдр и т. д. Многогранник Часара — невыпуклый многогранник с топологией тора — имеет в качестве скелета полный граф K 7 . [15] Каждый соседний многогранник в четырех или более измерениях также имеет полный скелет.
Все K1 – K4 являются плоскими графами . Однако каждый планарный рисунок полного графа с пятью и более вершинами должен содержать пересечение, а непланарный полный граф К5 играет ключевую роль в характеристиках планарных графов: по теореме Куратовского граф планарен тогда и только тогда, когда он не содержит ни K 5 , ни полного двудольного графа K 3,3 в качестве подразделения, и по теореме Вагнера тот же результат справедлив для миноров графа вместо подразделений. Как часть семейства Петерсенов , K6 играет роль одного из запрещенных второстепенных файлов для бессвязного встраивания . [16] Другими словами, как доказали Конвей и Гордон [17] , каждое вложение K 6 в трехмерное пространство внутренне связано, по крайней мере, с одной парой связанных треугольников. Конвей и Гордон также показали, что любое трехмерное вложение K 7 содержит гамильтонов цикл , вложенный в пространство как нетривиальный узел .
Примеры
Полные графы с вершинами от 1 до 12 показаны ниже вместе с количеством ребер:
Полный двудольный граф (или биклика ), специальный двудольный граф , в котором каждая вершина на одной стороне двудольного деления соединена с каждой вершиной на другой стороне.
Рекомендации
^ Банг-Йенсен, Йорген; Гутин, Грегори (2018), «Основная терминология, обозначения и результаты», в Bang-Jensen, Jørgen; Гутин, Грегори (ред.), Классы ориентированных графов , Монографии Springer по математике, Springer International Publishing, стр. 1–34, doi : 10.1007/978-3-319-71840-8_1; см. стр. 17
^ Кнут, Дональд Э. (2013), «Две тысячи лет комбинаторики», Уилсон, Робин; Уоткинс, Джон Дж. (ред.), Комбинаторика: древнее и современное , Oxford University Press, стр. 7–37, ISBN978-0191630620.
^ Mystic Rose, nrich.maths.org , получено 23 января 2012 г..
^ Хартнетт, Кевин. «Радужное доказательство показывает, что графики состоят из однородных частей». Журнал Кванта . Архивировано из оригинала 20 февраля 2020 г. Проверено 20 февраля 2020 г.
^ Хассани, М. «Циклы в графиках и нарушения». Математика. Газ. 88, 123–126, 2004.
^ Тичи, Роберт Ф.; Вагнер, Стефан (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 г..
^ Каллан, Дэвид (2009), Комбинаторный обзор тождеств для двойного факториала , arXiv : 0906.1317 , Bibcode : 2009arXiv0906.1317C.
^ Освин Айххольцер. «Проект «Прямолинейный перекресток». Архивировано из оригинала 30 апреля 2007 г.
^ Акош Часар, Многогранник без диагоналей. Архивировано 18 сентября 2017 г. в Wayback Machine , Институт Бояи, Сегедский университет, 1949 г.
^ Гарднер, Мартин (1988), Путешествие во времени и другие математические недоумения, WH Freeman and Company, стр. 140, Бибкод : 1988ttom.book.....G, ISBN0-7167-1924-Х
^ Робертсон, Нил ; Сеймур, Полиция ; Томас, Робин (1993), «Бесзвенные вложения графов в трехмерное пространство», Бюллетень Американского математического общества , 28 (1): 84–89, arXiv : math/9301216 , doi : 10.1090/S0273-0979-1993- 00335-5, МР 1164063, S2CID 1110662.