Повний граф

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

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

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

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

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

Complete graph K1.svg Complete graph K2.svg Complete graph K3.svg Complete graph K4.svg
Complete graph K5.svg Complete graph K6.svg Complete graph K7.svg Complete graph K8.svg
Complete graph K9.svg Complete graph K10.svg Complete graph K11.svg

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

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