Полный граф

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

Свойства

  • Полный граф с n вершинами имеет n (n - 1) / 2 ребер
  • Полный граф с n вершинами есть регулярным графом степени n - 1.
  • Графы K 1 - K 4 является планарными. Полные графы с большим количеством вершин не является планарными, поскольку содержат подграф K 5 и, следовательно, не удовлетворяют условия Куратовского.

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

K_1: 0K_2: 1K_3: 3K_4: 6
Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
K_5: 10K_6: 15K_7: 21K_8: 28
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg
K_9: 36K_ {10}: 45K_ {11}: 55
Complete graph K9.svg Complete graph K10.svg Complete graph K11.svg

Источники

  • Ф. Харари. Теория графов. М.: "Мир". 1973
  • Р.Уилсон. Введение в теорию графов. М.: Мир, 1977