Полный граф

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Полный граф
Complete graph K7.svg
K7, полный граф с 7 вершинами
Вершин n
Рёбер
Диаметр 1
Автоморфизмы n! (Sn)
Хроматическое число n
Хроматический индекс n если n - нечётное,
иначе n − 1
Обозначение Kn

По́лный граф — простой неориентированный граф, в котором каждая пара различных вершин смежна. Полный граф с вершинами имеет рёбер и обозначается . Является регулярным графом степени .

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

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

Графы с по являются планарными. Полные графы с большим количеством вершин не являются планарными, так как содержат подграф и, следовательно, не удовлетворяют критерию Понтрягина-Куратовского.

Примеры[править | править код]

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

K1: 0 K2: 1 K3: 3 K4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg 3-simplex graph.svg
K5: 10 K6: 15 K7: 21 K8: 28
4-simplex graph.svg 5-simplex graph.svg 6-simplex graph.svg 7-simplex graph.svg
K9: 36 K10: 45 K11: 55 K12: 66
8-simplex graph.svg 9-simplex graph.svg 10-simplex graph.svg 11-simplex graph.svg