Полный граф

Полный граф — это граф, в котором каждая пара различных вершин соединена ровно одним ребром. В теории графов полный граф является одним из фундаментальных понятий, представляя собой максимально связную структуру без петель и кратных рёбер. Полные графы обозначаются символом \(K_n\), где \(n\) — количество вершин. Например, \(K_3\) — это треугольник, \(K_4\) — тетраэдр (в трёхмерном представлении), а \(K_5\) — полный граф с пятью вершинами, который уже не является планарным.

Основные свойства

Количество рёбер

В полном графе \(K_n\) количество рёбер определяется числом сочетаний из \(n\) по 2: \[ \frac{n(n-1)}{2}. \] Эта формула следует из того, что каждая из \(n\) вершин соединяется с \(n-1\) другими, но каждое ребро учитывается дважды. Например, для \(K_5\) количество рёбер равно \(5 \cdot 4 / 2 = 10\).

Степени вершин

Каждая вершина в \(K_n\) имеет степень \(n-1\), то есть соединена со всеми остальными вершинами. Это делает полный граф регулярным графом степени \(n-1\).

Связность

Полный граф является \( (n-1) \)-связным: удаление любых \(n-2\) вершин не нарушает связности, а удаление \(n-1\) вершин оставляет одну изолированную вершину. Он также является \( (n-1) \)-рёберно-связным.

Хроматическое число

Хроматическое число полного графа \(K_n\) равно \(n\), так как для правильной раскраски вершин требуется \(n\) различных цветов — каждая вершина должна быть окрашена в свой цвет, чтобы смежные вершины не совпадали по цвету. Это максимальное хроматическое число среди всех графов с \(n\) вершинами.

Планарность

Полный граф \(K_n\) является планарным (то есть может быть изображён на плоскости без пересечения рёбер) только для \(n \le 4\). Для \(n = 5\) граф \(K_5\) не планарен, что является одним из двух базовых примеров в теореме Куратовского (наряду с \(K_{3,3}\)). \(K_5\) — это минимальный по числу вершин не планарный граф.

Гамильтоновы и эйлеровы циклы

Полный граф \(K_n\) при \(n \ge 3\) является гамильтоновым: в нём существует цикл, проходящий через каждую вершину ровно один раз. Более того, число различных гамильтоновых циклов в \(K_n\) равно \(\frac{(n-1)!}{2}\). Эйлеров цикл (проходящий каждое ребро ровно один раз) существует в \(K_n\) тогда и только тогда, когда все вершины имеют чётную степень, то есть когда \(n\) нечётно (так как степень каждой вершины \(n-1\) должна быть чётной). Таким образом, \(K_n\) является эйлеровым при нечётных \(n \ge 3\).

Классификация и частные случаи

Полные графы малых размеров

• \(K_1\) — граф с одной вершиной и без рёбер (тривиальный граф).
• \(K_2\) — простое ребро, соединяющее две вершины.
• \(K_3\) — треугольник, который является циклом длины 3.
• \(K_4\) — полный граф на четырёх вершинах; он планарен и изоморфен графу тетраэдра.

Полные графы как подграфы

Полный граф \(K_n\) может быть подграфом более крупных графов. Наличие \(K_n\) в качестве подграфа называется кликой размера \(n\). Задача поиска максимальной клики в графе является NP-полной.

Полные двудольные графы

Родственным понятием является полный двудольный граф \(K_{m,n}\), в котором вершины разбиты на две доли, и каждая вершина одной доли соединена со всеми вершинами другой доли. Полный граф \(K_n\) можно рассматривать как частный случай полного многодольного графа с одной долей.

Применение

Теория графов и комбинаторика

Полные графы служат эталоном для сравнения плотности графов. Они используются в задачах о раскраске графов, теории Рамсея (где изучаются условия, при которых в произвольном графе обязательно содержится \(K_n\) или его дополнение), а также в анализе сетей.

Информатика и сети

В компьютерных сетях полные графы моделируют топологию «полносвязной сети» (mesh topology), где каждый узел напрямую соединён с каждым. Такая топология обеспечивает высокую отказоустойчивость и минимальную задержку, но требует большого числа соединений (порядка \(O(n^2)\)), что делает её дорогой для больших сетей.

Математическое моделирование

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

Социальные сети и теория графов

В социологии полный граф может представлять группу, в которой каждый член взаимодействует с каждым (например, в малых группах). Такая структура называется «кликой» в анализе социальных сетей.

Интересные факты

• Число различных полных графов с \(n\) вершинами (с точностью до изоморфизма) равно 1 для каждого \(n\), так как все полные графы с одинаковым числом вершин изоморфны.
• Полный граф \(K_5\) является минимальным не планарным графом. Теорема Куратовского утверждает, что граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного \(K_5\) или \(K_{3,3}\).
• В теории Рамсея число Рамсея \(R(3,3)\) равно 6: любой граф с 6 вершинами либо содержит треугольник (\(K_3\)), либо его дополнение содержит треугольник.
• Полный граф \(K_n\) имеет ровно \(n^{n-2}\) остовных деревьев (по формуле Кэли).

Критика и ограничения

Полные графы редко встречаются в реальных сетях из-за высокой стоимости соединений. Например, в социальных сетях редко бывает, чтобы каждый человек знал каждого другого. Поэтому полные графы чаще используются как теоретические модели или как предельные случаи при анализе плотности графов. В задачах оптимизации полные графы могут быть неэффективны для алгоритмов, работающих с разреженными графами, так как число рёбер растёт квадратично.