Полный граф

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Полный граф
K7, полный граф с 7 вершинами
K7, полный граф с 7 вершинами
Вершин

n

Рёбер

\frac{n (n-1)}{2}

Диаметр

1

Автоморфизмы

n! (Sn)

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

n

Хроматический индекс

n если n - нечётное,
иначе n − 1

Обозначение

Kn

Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с n вершинами имеет n(n-1)/2 рёбер и обозначается K_n. Является регулярным графом степени n-1.

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

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

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

Ниже приведены полные графы с числом вершин от 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