Лекция: Полные графы и деревья

Граф называется полным, если любые две его вершины смежены, т.е. имеют общее ребро.

1

5 2

— К5

Теорема: В полном графе с n вершинами ребер.

Доказательство. Каждая из n вершин полного графа связана с n-1

. вершинами, то есть n(n-1).

При таком подходе каждое из ребер учитывается дважды, поэтому надо разделить произведение на два.

В полном графе всегда существует гамильтонов цикл, и он определяется любой циклической подстановкой (см. теорию групп).

Граф G называетсядополнением графа G, если их объединение дает полный граф.

1 2 1 2

G G

4 3 4 3

1 1

5 2 4 3

G G

4 3 2 5