Повний граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Повний графпростий граф, в якому кожна пара різних вершин суміжна, тобто існує ребро, що сполучає ці вершини. Повний граф зазвичай позначається Kn.

Властивості[ред.ред. код]

  • Повний граф з n вершинами має n(n - 1)/ 2 ребер
  • Повний граф з n вершинами є регулярним графом степеня n - 1.
  • Графи K1 — K4 є планарними. Повні графи з більшою кількістю вершин не є планарними, оскільки містять підграф K5 і, отже, не задовольняють умови Куратовського.

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

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

Джерела[ред.ред. код]

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