Полный граф

Поделись знанием:
Перейти к: навигация, поиск
Полный граф

K7, полный граф с 7 вершинами
Вершин

n

Рёбер

<math>\frac{n (n-1)}{2}</math>

Диаметр

1

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

n! (Sn)

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

n

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

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

Обозначение

Kn

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

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

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



Примеры

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

Напишите отзыв о статье "Полный граф"

Отрывок, характеризующий Полный граф

В то время как это происходило в Петербурге, французы уже прошли Смоленск и все ближе и ближе подвигались к Москве. Историк Наполеона Тьер, так же, как и другие историки Наполеона, говорит, стараясь оправдать своего героя, что Наполеон был привлечен к стенам Москвы невольно. Он прав, как и правы все историки, ищущие объяснения событий исторических в воле одного человека; он прав так же, как и русские историки, утверждающие, что Наполеон был привлечен к Москве искусством русских полководцев. Здесь, кроме закона ретроспективности (возвратности), представляющего все прошедшее приготовлением к совершившемуся факту, есть еще взаимность, путающая все дело. Хороший игрок, проигравший в шахматы, искренно убежден, что его проигрыш произошел от его ошибки, и он отыскивает эту ошибку в начале своей игры, но забывает, что в каждом его шаге, в продолжение всей игры, были такие же ошибки, что ни один его ход не был совершенен. Ошибка, на которую он обращает внимание, заметна ему только потому, что противник воспользовался ею. Насколько же сложнее этого игра войны, происходящая в известных условиях времени, и где не одна воля руководит безжизненными машинами, а где все вытекает из бесчисленного столкновения различных произволов?
После Смоленска Наполеон искал сражения за Дорогобужем у Вязьмы, потом у Царева Займища; но выходило, что по бесчисленному столкновению обстоятельств до Бородина, в ста двадцати верстах от Москвы, русские не могли принять сражения. От Вязьмы было сделано распоряжение Наполеоном для движения прямо на Москву.
Moscou, la capitale asiatique de ce grand empire, la ville sacree des peuples d'Alexandre, Moscou avec ses innombrables eglises en forme de pagodes chinoises! [Москва, азиатская столица этой великой империи, священный город народов Александра, Москва с своими бесчисленными церквами, в форме китайских пагод!] Эта Moscou не давала покоя воображению Наполеона. На переходе из Вязьмы к Цареву Займищу Наполеон верхом ехал на своем соловом энглизированном иноходчике, сопутствуемый гвардией, караулом, пажами и адъютантами. Начальник штаба Бертье отстал для того, чтобы допросить взятого кавалерией русского пленного. Он галопом, сопутствуемый переводчиком Lelorgne d'Ideville, догнал Наполеона и с веселым лицом остановил лошадь.