Повний граф

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

Властивості

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

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

$K_{1}:0$	$K_{2}:1$	$K_{3}:3$	$K_{4}:6$

$K_{5}:10$	$K_{6}:15$	$K_{7}:21$	$K_{8}:28$

$K_{9}:36$	$K_{10}:45$	$K_{11}:55$

Джерела

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.