WikiSort.ru - Не сортированное

Полный граф
K7, полный граф с 7 вершинами
Вершин	n
Рёбер	${\displaystyle {\frac {n(n-1)}{2}}}$
Диаметр	1
Автоморфизмы	n! (Sn)
Хроматическое число	n
Хроматический индекс	n если n - нечётное, иначе n − 1
Обозначение	Kn

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

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

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

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

Примеры

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

K1: 0	K2: 1	K3: 3	K4: 6
K5: 10	K6: 15	K7: 21	K8: 28
K9: 36	K10: 45	K11: 55	K12: 66