Полный граф

27.07.2023

Полный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный ориентированный граф — ориентированный граф, в котором каждая пара различных вершин соединена парой ребер с противоположными ориентациями. Принято считать, что теория графов берет свое начало с решения Леонардом Эйлером задачи о семи кёнигсбергских мостах, датированного 1736 годом, однако изображения полных графов, вершины которых располагаются в вершинах правильных многоугольников, встречаются ещё в 13 веке, в работе Раймунда Луллия. Подобные рисунки иногда называют мистическими розами.

Полный граф K 9 {displaystyle K_{9}} на рисунке из труда Ars Magna Раймунда Луллия.

Обычно полный граф с n n вершинами обозначается через K n K_{n} . Некоторые источники утверждают, что буква K K в этом обозначении является сокращением от немецкого слова нем. komplett, в переводе на русский – «полный, целый», однако оригинальное название полного графа на немецком, нем. vollständiger Graph, не содержит буквы K K . По другой версии, такое обозначение полному графу было дано в честь Казимежа Куратовского, подчеркивая его вклад в развитие теории графов.

Комбинаторные свойства

Полный граф с n n вершинами имеет n ( n − 1 ) / 2 n(n-1)/2 рёбер, это треугольное число.

Полный граф с n n вершинами является регулярным графом степени n − 1 n-1 .

Любой полный граф является своей максимальной кликой.

Граф K n K_{n} является ( n − 1 ) (n-1) -связным.

Дополнение графа K n K_{n} – это пустой граф, то есть граф без рёбер.

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

В полном графе не может быть независимого множества более чем из одной вершины.

Пусть n ∈ N {displaystyle nin mathbb {N} } , а T 1 , T 2 , … , T n {displaystyle ,T_{1},T_{2},dots ,T_{n}} – семейство деревьев ограниченных степеней, где для любого i ∈ { 1 , 2 , … n } {displaystyle iin {1,2,dots n}} число вершин дерева T i T_{i} равно i i . Тогда граф K n K_{n} можно разложить на деревья T 1 , T 2 , … , T n {displaystyle ,T_{1},T_{2},dots ,T_{n}} , то есть существуют попарно рёберно-непересекающиеся копии графов T 1 , T 2 , … , T n {displaystyle ,T_{1},T_{2},dots ,T_{n}} в графе K n K_{n} , и каждое ребро графа K n K_{n} принадлежит хотя бы одной из этих копий.

Число различных путей между двумя выделенными вершинами в полном графе K n + 2 {displaystyle K_{n+2}} вычисляется по формуле w n + 2 = n ! e n = ⌊ e n ! ⌋ {displaystyle w_{n+2}=n!e_{n}=lfloor en! floor } , где через e e обозначена постоянная Эйлера, и e n = ∑ k = 0 n 1 k ! . {displaystyle e_{n}=sum _{k=0}^{n}{frac {1}{k!}}.}

Индексы Хосойи (полные числа паросочетаний) полного графа являются телефонными числами ( n n -ое телефонное число – это число различных вариантов, которыми из n n человек можно выбрать набор пар людей, которые будут одновременно созваниваться друг с другом по телефону; в частности можно выбрать пустой набор), причем на полных графах реализуются максимально возможные значения индекса Хосойи для n n -вершинного графа. Эти индексы образуют последовательность 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... последовательность A000085 в OEIS.

Число совершенных паросочетаний графа K n K_{n} с чётным n n определяется с помощью двойного факториала и равняется ( n − 1 ) ! ! {displaystyle (n-1)!!} .

Теорема Рамсея: Для любых c c натуральных чисел n 1 , n 2 , … , n c {displaystyle n_{1},n_{2},dots ,n_{c}} в любой c c -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с n i n_{i} вершинами для некоторого цвета i i . В частности, для любых r r и s s , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из r r вершин, либо полный белый подграф из s s вершин.

Теорема Турана: Обозначим через ex ( v , n ) {displaystyle { extrm {ex}}(v,n)} максимальное количество рёбер, которое может иметь граф с v v вершинами, не содержащий подграфа, изоморфного K n K_{n} . Тогда, если v = m ( n − 1 ) + r v=m(n-1)+r , где r r — остаток от деления v v на n − 1 n-1 , то этот максимум равен ex ( v , n ) = ( n − 2 ) ( v 2 − r 2 ) 2 n − 2 + r ( r − 1 ) 2 . {displaystyle { extrm {ex}}(v,n)={frac {(n-2)(v^{2}-r^{2})}{2n-2}}+{frac {r(r-1)}{2}}.} Среди всех графов на v v вершинах, не содержащих подграфа K n K_{n} , этот максимум по количеству рёбер достигается на графе T n ( v ) T_{n}(v) , определяемом следующим образом. Пусть T n ( v ) T_{n}(v) это граф с v v вершинами, разобьём все вершины на n − 1 n-1 «почти равных» групп (то есть возьмём r r групп по m + 1 m+1 вершине и n − 1 − r n-1-r групп по m m вершин, если v : ( n − 1 ) = m v:(n-1)=m с остатком r r ) и соединим рёбрами все пары вершин из разных групп. Таким образом получим ( n − 1 ) (n-1) -дольный граф.

Теорема Кэли о числе деревьев: Число остовных деревьев в полном графе K n K_{n} равно n n − 2 . {displaystyle n^{n-2}.}

Геометрические и топологические свойства

Число пересечений

Известна верхняя оценка на число пересечений полного графа, а именно cr ( K n ) ≤ 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ {displaystyle { extrm {cr}}(K_{n})leq { frac {1}{4}}leftlfloor { frac {n}{2}} ight floor leftlfloor { frac {n-1}{2}} ight floor leftlfloor { frac {n-2}{2}} ight floor leftlfloor { frac {n-3}{2}} ight floor } . Впервые, в конце пятидесятых, вопрос о существовании такой оценки выдвинул Энтони Хилл, известный британский художник-абстракционист. Ему удалось разработать несколько особых методов изображения полных графов, позволивших в дальнейшем эффективно исследовать их числа пересечений. Один из таких методов известен как «рисунок на алюминиевой банке», а другой – как «изображения Харари-Хилла». Анализируя эти методы изображения математикам Блажеку и Коману удалось подтвердить оценку Хилла для всех полных графов в 1964 году. Стоит отметить, что Хилл выдвинул куда более сильную гипотезу, а именно cr ( K n ) = 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ {displaystyle { extrm {cr}}(K_{n})={ frac {1}{4}}leftlfloor { frac {n}{2}} ight floor leftlfloor { frac {n-1}{2}} ight floor leftlfloor { frac {n-2}{2}} ight floor leftlfloor { frac {n-3}{2}} ight floor } . Эта гипотеза известна как гипотеза Хилла и на данный момент подтверждена только для нескольких малых n n . Гипотезу Хилла иногда называют гипотезой Гая, в честь британского математика Ричарда Гая, в чьей работе за 1960 год содержатся прямые намеки на данный вопрос, или гипотезой Харари-Хилла, так как работа Энтони Хилла и Фрэнка Харари за 1963 год, видимо, самая ранняя опубликованная математическая статья, содержащая точную формулировку этой гипотезы. Полные графы K n K_{n} при n ≤ 4 nleq 4 являются планарными, то есть их число пересечений равно 0. В 1972 году Гай показал, что гипотеза Хилла верна для всех n ≤ 10 {displaystyle nleq 10} , а в 2007 году Шэнджунь Пэн и Брюс Рихтер подтвердили гипотезу Хилла для n = 11 , 12 {displaystyle n=11,12} . В 2015 году Дэн Макуиллан, Шэнджунь Пэн и Брюс Рихтер выяснили, что cr ( K 13 ) {displaystyle { extrm {cr}}(K_{13})} является нечетным числом, лежащим между 219 и 225 включительно. Вся известная на данный момент информация о точных значениях чисел пересечений полных графов представлена в таблице ниже.

Кроме того, в 1969 году Гай получил нижнюю оценку на число пересечений полного графа, а именно cr ( K n ) ≥ 1 120 n ( n − 1 ) ( n − 2 ) ( n − 3 ) {displaystyle { extrm {cr}}(K_{n})geq { frac {1}{120}}n(n-1)(n-2)(n-3)} . При этом, ещё в 1960 году он обнаружил, что существует предел lim n → ∞ cr ( K n ) / Z ( n ) {displaystyle lim _{n o infty }{{ extrm {cr}}(K_{n})/Z(n)}} , где Z ( n ) = 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ {displaystyle Z(n)={ frac {1}{4}}leftlfloor { frac {n}{2}} ight floor leftlfloor { frac {n-1}{2}} ight floor leftlfloor { frac {n-2}{2}} ight floor leftlfloor { frac {n-3}{2}} ight floor } , а в 2007 году Этьен де Клерк, Дмитрий Пасечник и Александр Схрейвер выяснили, что верна оценка

lim n → ∞ cr ( K n ) Z ( n ) ≥ 0.8594 {displaystyle lim _{n o infty }{frac {{ extrm {cr}}(K_{n})}{Z(n)}}geq 0.8594} .

Число прямолинейных пересечений

Для n ≤ 7 {displaystyle nleq 7} и n = 9 n=9 число прямолинейных пересечений графа K n K_{n} , которое обычно обозначается через rcr ( K n ) {displaystyle { extrm {rcr}}(K_{n})} , совпадает с его обыкновенным числом пересечений. Однако, число прямолинейных пересечений графа K 8 K_{8} равно 19 19 , тогда как cr ( K 8 ) = 18 {displaystyle { extrm {cr}}(K_{8})=18} . В 2001 году Алекс Бродский, Стефан Дуроше и Эллен Гетнер выяснили, что число прямолинейных пересечений графа K 10 {displaystyle K_{10}} равно 62, при cr ( K 10 ) = 60 {displaystyle { extrm {cr}}(K_{10})=60} . На данный момент точные значения rcr ( K n ) {displaystyle { extrm {rcr}}(K_{n})} известны для n ≤ 27 {displaystyle nleq 27} и n = 30 {displaystyle n=30} . Суть точного вычисления заключается в нахождении соответствующих (и совпадающих) нижних и верхних оценок. Нижние оценки для n ≤ 27 {displaystyle nleq 27} были построены совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром в 2012 году, нижняя оценка для n = 30 {displaystyle n=30} построена совместно математиками Марио Сетина, Сесаром Эрнандес-Велесом, Хесусом Леаньосом и Кристобалем Вильялобос Гильеном в 2012 году, а все верхние оценки получены австрийским математиком Освином Айххольцером. Кроме того, Айххольцер опубликовал на своем сайте суммарную информацию обо всех известных на данный момент нижних и верхних оценках на rcr ( K n ) {displaystyle { extrm {rcr}}(K_{n})} вплоть до n = 100 {displaystyle n=100} . Ниже приведена таблица с соответствующими оценками для 5 ≤ n ≤ 30 {displaystyle 5leq nleq 30} .

В 1994 году Эдвард Р. Шайнерман и Герберт С. Уилф обнаружили неожиданную связь между числом прямолинейных пересечений графа K n K_{n} и задачей Сильвестра "о четырех точках" из вероятностной геометрии. Пусть R R — открытое множество на плоскости с конечной мерой Лебега. Обозначим через q ( R ) {displaystyle { extrm {q}}(R)} вероятность того, что если в R R равномерно и случайно выбраны четыре точки независимо друг от друга, то их выпуклая оболочка является четырехугольником, а через q ∗ {displaystyle { extrm {q}}^{*}} – инфимум значений q ( R ) {displaystyle { extrm {q}}(R)} по всем таким R R . Тогда верно равенство

lim n → ∞ rcr ( K n ) ( n 4 ) = q ∗ , {displaystyle lim _{n o infty }{frac {{ extrm {rcr}}(K_{n})}{n choose 4}}={ extrm {q}}^{*},}

где ( n 4 ) {displaystyle {n choose 4}} обозначает соответствующий биномиальный коэффициент. Продолжительное время уточнялись верхняя и нижняя оценки на константу q ∗ {displaystyle { extrm {q}}^{*}} , и на данный момент лучшая нижняя и лучшая верхняя оценки получены совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром, и составляют

0.379972 < 277 729 ≤ q ∗ ≤ 83247328 218791125 < 0.380488. {displaystyle 0.379972<{frac {277}{729}}leq { extrm {q}}^{*}leq {frac {83247328}{218791125}}<0.380488.} Книжное вложение с тремя страницами для графа K 5 K_{5}

Планарность и книжная толщина

Графы с K 1 K_{1} по K 4 K_{4} являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф K 5 K_{5} и, следовательно, не удовлетворяют критерию Понтрягина — Куратовского.

При n ≤ 6 {displaystyle nleq 6} граф K n K_{n} является 1-планарным графом, но при n ≥ 7 {displaystyle ngeq 7} граф K n K_{n} не является 1-планарным.

Книжная толщина графа K 5 K_{5} равна 3 3 . Для любых n ≥ 4 ngeq 4 граф K n K_{n} имеет книжную толщину в точности ⌈ n / 2 ⌉ {displaystyle lceil n/2 ceil } .

Симплексы и многогранники

Интерактивное изображение многогранника Часара. Водите мышью влево и вправо чтобы поворачивать SVG изображение.

Полный граф образуется из вершин и ребер (n-1)-симплекса. Так, например, геометрически K 3 K_{3} образует множество вершин и ребер треугольника, K 4 K_{4} – тетраэдра и так далее. Объединение всех семи вершин и двадцати одного ребра многогранника Часара, топологически эквивалентного тору, образует полный граф K 7 {displaystyle K_{7}} .

Граф 2-смежностного многогранника является полным графом.

Зацепленность и заузленность

Граф K 6 K_{6} не имеет незацепленного вложения, а более точно, как доказали Джон Хортон Конвей и Кэмерон Гордон в 1983 году, для любого вложения K 6 K_{6} в трехмерное пространство существует два таких цикла в K 6 K_{6} , образы которых при вложении имеют нечетный коэффициент зацепления. А для любого вложения графа K 7 {displaystyle K_{7}} в трехмерное пространство существует такой гамильтонов цикл в K 7 {displaystyle K_{7}} , образ которого при вложении имеет нетривиальный инвариант Арфа, то есть является нетривиальным узлом. В 2002 году Эрика Флапан доказала, что для любого m ∈ N {displaystyle min mathbb {N} } найдется такое n ∈ N nin {mathbb {N} } , что каждое вложение графа K n K_{n} в R 3 mathbb {R} ^{3} содержит двукомпонентое зацепление, коэффициент зацепления которого равен m m . А кроме того, для любого m ∈ N {displaystyle min mathbb {N} } найдется такое r ∈ N {displaystyle rin mathbb {N} } , что каждое вложение графа K n K_{n} в R 3 mathbb {R} ^{3} содержит узел Q Q , такой что | a 2 ( Q ) | ≥ m {displaystyle |a_{2}(Q)|geq m} , где через a 2 ( Q ) {displaystyle a_{2}(Q)} обозначен второй коэффициент многочлена Конвея узла Q Q .

Примеры

Ниже приведены полные графы с числом вершин от 1 до 12 и количества их рёбер.