Русская Википедия:Полный граф

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Файл:Ramon Llull - Ars Magna Fig 1.png
Полный граф <math> K_9 </math> на рисунке из труда Ars Magna Раймунда Луллия.

Обычно полный граф с <math>n</math> вершинами обозначается через <math>K_n</math>. Некоторые источники утверждают, что буква <math>K</math> в этом обозначении является сокращением от немецкого слова Шаблон:Lang-de,Шаблон:Sfn в переводе на русский – «полный, целый», однако оригинальное название полного графа на немецком, Шаблон:Lang-de, не содержит буквы <math>K</math>. По другой версии, такое обозначение полному графу было дано в честь Казимежа Куратовского, подчеркивая его вклад в развитие теории графов.Шаблон:Sfn

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

  • Полный граф, каждое ребро которого снабжено ориентацией, называется турниром.
  • Пусть <math>n\in\mathbb{N}</math>, а <math>\,T_1,T_2,\dots,T_n</math> – семейство деревьев ограниченных степеней, где для любого <math>i\in\{1,2,\dots n\} </math> число вершин дерева <math>T_i</math> равно <math>i</math>. Тогда граф <math>K_n</math> можно разложить на деревья <math>\,T_1,T_2,\dots,T_n</math>, то есть существуют попарно рёберно-непересекающиеся копии графов <math>\,T_1,T_2,\dots,T_n</math> в графе <math>K_n</math>, и каждое ребро графа <math>K_n</math> принадлежит хотя бы одной из этих копий.Шаблон:Sfn
  • Число различных путей между двумя выделенными вершинами в полном графе <math>K_{n+2}</math> вычисляетсяШаблон:Sfn по формуле <math> w_{n+2} = n! e_n = \lfloor en!\rfloor</math>, где через <math>e</math> обозначена постоянная Эйлера, и
    <math>e_n = \sum_{k=0}^n\frac{1}{k!}.</math>
  • Индексы Хосойи (полные числа паросочетаний) полного графа являются Шаблон:Нп5 (<math>n</math>-ое телефонное число – это число различных вариантов, которыми из <math>n</math> человек можно выбрать набор пар людей, которые будут одновременно созваниваться друг с другом по телефону; в частности можно выбрать пустой набор), причем на полных графах реализуются максимально возможные значения индекса Хосойи для <math>n</math>-вершинного графа.Шаблон:Sfn Эти индексы образуют последовательность
    1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... Шаблон:OEIS.
  • Теорема Рамсея: Для любых <math>c</math> натуральных чисел <math>n_1, n_2,\dots, n_c</math> в любой <math>c</math>-цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с <math>n_i</math> вершинами для некоторого цвета <math>i</math>. В частности, для любых <math>r</math> и <math>s</math>, достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из <math>r</math> вершин, либо полный белый подграф из <math>s</math> вершин.Шаблон:Sfn
  • Теорема Турана: Обозначим через <math>\textrm{ex}(v,n)</math> максимальное количество рёбер, которое может иметь граф с <math>v</math> вершинами, не содержащий подграфа, изоморфного <math>K_n</math>. Тогда, если <math>v=m(n-1)+r</math>, где <math>r</math> — остаток от деления <math>v</math> на <math>n-1</math>, то этот максимум равен <math>\textrm{ex}(v,n)=\frac{(n-2)(v^2-r^2)}{2n-2} + \frac{r(r-1)}{2}.</math> Среди всех графов на <math>v</math> вершинах, не содержащих подграфа <math>K_n</math>, этот максимум по количеству рёбер достигается на графе <math>T_n(v)</math>, определяемом следующим образом. Пусть <math>T_n(v)</math> это граф с <math>v</math> вершинами, разобьём все вершины на <math>n-1</math> «почти равных» групп (то есть возьмём <math>r</math> групп по <math>m+1</math> вершине и <math>n-1-r</math> групп по <math>m</math> вершин, если <math>v:(n-1)=m</math> с остатком <math>r</math>) и соединим рёбрами все пары вершин из разных групп. Таким образом получим <math>(n-1)</math>-дольный граф.Шаблон:Sfn

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

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

Известна верхняя оценка на число пересечений полного графа, а именно <math>\textrm{cr}(K_n) \le \tfrac{1}{4} \left\lfloor\tfrac{n}{2}\right\rfloor\left\lfloor\tfrac{n-1}{2}\right\rfloor\left\lfloor\tfrac{n-2}{2}\right\rfloor\left\lfloor\tfrac{n-3}{2}\right\rfloor</math>. Впервые, в конце пятидесятых, вопрос о существовании такой оценки выдвинул Энтони Хилл,Шаблон:Sfn известный британский художник-абстракционист. Ему удалось разработать несколько особых методов изображения полных графов, позволивших в дальнейшем эффективно исследовать их числа пересечений. Один из таких методов известен как «рисунок на алюминиевой банке», а другой – как «изображения Харари-Хилла».Шаблон:Sfn Анализируя эти методы изображения математикам Блажеку и Коману удалось подтвердитьШаблон:Sfn оценку Хилла для всех полных графов в 1964 году. Стоит отметить, что Хилл выдвинул куда более сильную гипотезу, а именно <math>\textrm{cr}(K_n) = \tfrac{1}{4} \left\lfloor\tfrac{n}{2}\right\rfloor\left\lfloor\tfrac{n-1}{2}\right\rfloor\left\lfloor\tfrac{n-2}{2}\right\rfloor\left\lfloor\tfrac{n-3}{2}\right\rfloor</math>. Эта гипотеза известна как гипотеза Хилла и на данный момент подтверждена только для нескольких малых <math>n</math>.Шаблон:Sfn Гипотезу Хилла иногда называют гипотезой Гая, в честь британского математика Ричарда Гая, в чьей работеШаблон:Sfn за 1960 год содержатся прямые намеки на данный вопрос, или гипотезой Харари-Хилла, так как работаШаблон:Sfn Энтони Хилла и Фрэнка Харари за 1963 год, видимо, самая ранняя опубликованная математическая статья, содержащая точную формулировку этой гипотезы.Шаблон:Sfn Полные графы <math>K_n</math> при <math>n\le 4</math> являются планарными, то есть их число пересечений равно 0. В 1972 году Гай показал,Шаблон:Sfn что гипотеза Хилла верна для всех <math>n\le 10</math>, а в 2007 году Шэнджунь Пэн и Брюс Рихтер подтвердилиШаблон:Sfn гипотезу Хилла для <math>n=11, 12</math>. В 2015 году Дэн Макуиллан, Шэнджунь Пэн и Брюс Рихтер выяснили,Шаблон:Sfn что <math>\textrm{cr}(K_{13})</math> является нечетным числом, лежащим между 219 и 225 включительно. Вся известная на данный момент информация о точных значениях чисел пересечений полных графов представлена в таблице ниже.

Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center
<math>\textrm{cr}(G)</math> Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center

Кроме того, в 1969 году Гай получилШаблон:Sfn нижнюю оценку на число пересечений полного графа, а именно <math>\textrm{cr}(K_n) \ge \tfrac{1}{120} n(n-1)(n-2)(n-3)</math>. При этом, ещё в 1960 году он обнаружил,Шаблон:Sfn что существует предел <math>\lim_{n\to\infty} {\textrm{cr}(K_n)/Z(n)}</math>, где <math>Z(n)=\tfrac{1}{4} \left\lfloor\tfrac{n}{2}\right\rfloor\left\lfloor\tfrac{n-1}{2}\right\rfloor\left\lfloor\tfrac{n-2}{2}\right\rfloor\left\lfloor\tfrac{n-3}{2}\right\rfloor</math>, а в 2007 году Этьен де Клерк, Дмитрий Пасечник и Александр Схрейвер выяснили,Шаблон:Sfn что верна оценка

<math>\lim_{n\to\infty} {\frac{\textrm{cr}(K_n)}{Z(n)}}\ge 0.8594</math>.

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

Для <math>n\le 7</math> и <math>n=9</math> число прямолинейных пересечений графа <math>K_n</math>, которое обычно обозначается через <math>\textrm{rcr}(K_n)</math>, совпадает с его обыкновенным числом пересечений. Однако, число прямолинейных пересечений графа <math>K_8</math> равно <math>19</math>, тогда как <math>\textrm{cr}(K_8)=18</math>.Шаблон:Sfn В 2001 году Алекс Бродский, Стефан Дуроше и Шаблон:Нп5 выяснили,Шаблон:Sfn что число прямолинейных пересечений графа <math>K_{10}</math> равно 62, при <math>\textrm{cr}(K_{10})=60</math>. На данный момент точные значения <math>\textrm{rcr}(K_n)</math> известны для <math>n\le 27</math> и <math>n=30</math>. Суть точного вычисления заключается в нахождении соответствующих (и совпадающих) нижних и верхних оценок. Нижние оценки для <math>n\le 27</math> были построеныШаблон:Sfn совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром в 2012 году, нижняя оценка для <math>n=30</math> построенаШаблон:Sfn совместно математиками Марио Сетина, Сесаром Эрнандес-Велесом, Хесусом Леаньосом и Кристобалем Вильялобос Гильеном в 2012 году, а все верхние оценки получены австрийским математиком Освином АйххольцеромШаблон:Sfn. Кроме того, Айххольцер опубликовалШаблон:Sfn на своем сайте суммарную информацию обо всех известных на данный момент нижних и верхних оценках на <math>\textrm{rcr}(K_{n})</math> вплоть до <math>n=100</math>. Ниже приведена таблица с соответствующими оценками для <math>5\le n \le 30</math>.

Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center
<math>\textrm{rcr}(G)</math> Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center Шаблон:Center

В 1994 году Шаблон:Нп5 и Шаблон:Нп5 обнаружилиШаблон:Sfn неожиданную связь между числом прямолинейных пересечений графа <math>K_n</math> и задачей Сильвестра "о четырех точках" из вероятностной геометрии.Шаблон:Sfn Пусть <math>R</math> — открытое множество на плоскости с конечной мерой Лебега. Обозначим через <math>\textrm{q}(R)</math> вероятность того, что если в <math>R</math> равномерно и случайно выбраны четыре точки независимо друг от друга, то их выпуклая оболочка является четырехугольником, а через <math>\textrm{q}^{*}</math> – инфимум значений <math>\textrm{q}(R)</math> по всем таким <math>R</math>. Тогда верно равенство

<math>\lim_{n\to\infty}{\frac{\textrm{rcr}(K_n)}Шаблон:N \choose 4}=\textrm{q}^{*},</math>

где <math>{n \choose 4}</math> обозначает соответствующий биномиальный коэффициент. Продолжительное время уточнялисьШаблон:Sfn верхняя и нижняя оценки на константу <math>\textrm{q}^{*}</math>, и на данный момент лучшая нижняяШаблон:Sfn и лучшая верхняяШаблон:Sfn оценки получены совместно математиками Бернардо Абрего, Сильвией Фернандес-Мерчант, Хесусом Леаньосом и Геласио Салазаром, и составляют

<math>0.379972<\frac{277}{729}\le\textrm{q}^{*}\le\frac{83247328

}{218791125}<0.380488.</math>

Файл:3page K5.svg
Книжное вложение с тремя страницами для графа <math>K_5</math>

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

Графы с <math>K_1</math> по <math>K_4</math> являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф <math>K_5</math> и, следовательно, не удовлетворяют критерию Понтрягина — Куратовского.Шаблон:Sfn

При <math>n\le 6</math> граф <math>K_n</math> является 1-планарным графом, но при <math>n\ge 7</math> граф <math>K_n</math> не является 1-планарным.Шаблон:Sfn

Книжная толщина графа <math>K_5</math> равна <math>3</math>. Для любых <math>n\ge 4</math> граф <math>K_n</math> имеет книжную толщину в точности <math>\lceil n/2\rceil</math>.Шаблон:Sfn

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

Файл:Csaszar polyhedron 3D model.svg
Интерактивное изображение многогранника Часара. Водите мышью влево и вправо чтобы поворачивать [ SVG изображение].

Полный граф образуется из вершин и ребер (n-1)-симплекса. Так, например, геометрически <math>K_3</math> образует множество вершин и ребер треугольника, <math>K_4</math> – тетраэдра и так далее. Объединение всех семи вершин и двадцати одного ребра многогранника Часара, топологически эквивалентного тору, образует полный граф <math>K_7</math>.

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

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

Граф <math>K_6</math> не имеет незацепленного вложения, а более точно, как доказали Джон Хортон Конвей и Шаблон:Нп5 в 1983 году, для любого вложения <math>K_6</math> в трехмерное пространство существует два таких цикла в <math>K_6</math>, образы которых при вложении имеют нечетный коэффициент зацепления.Шаблон:Sfn А для любого вложения графа <math>K_7</math> в трехмерное пространство существует такой гамильтонов цикл в <math>K_7</math>, образ которого при вложении имеет нетривиальный Шаблон:Нп5, то есть является нетривиальным узлом.Шаблон:Sfn В 2002 году Шаблон:Нп5 доказала, что для любого <math>m\in\mathbb{N}</math> найдется такое <math>n\in \mathbb{N}</math>, что каждое вложение графа <math>K_n</math> в <math>\mathbb{R}^3</math> содержит двукомпонентое зацепление, коэффициент зацепления которого равен <math>m</math>.Шаблон:Sfn А кроме того, для любого <math>m\in\mathbb{N}</math> найдется такое <math>r\in \mathbb{N}</math>, что каждое вложение графа <math>K_n</math> в <math>\mathbb{R}^3</math> содержит узел <math>Q</math>, такой что <math>|a_2(Q)|\ge m</math>, где через <math>a_2(Q)</math> обозначен второй коэффициент многочлена Конвея узла <math>Q</math>.Шаблон:Sfn

Примеры

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

Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math
Файл:Complete graph K1.svg Файл:Complete graph K2.svg Файл:Complete graph K3.svg Файл:3-simplex graph.svg Файл:4-simplex graph.svg Файл:5-simplex graph.svg
Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math Шаблон:Math
Файл:6-simplex graph.svg Файл:7-simplex graph.svg Файл:8-simplex graph.svg Файл:9-simplex graph.svg Файл:10-simplex graph.svg Файл:11-simplex graph.svg

Примечания

Шаблон:Примечания

Литература


Шаблон:Refend