Полные графы и деревья

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

1

5 2

- К₅

4 3

n(n-1)

Теорема: В полном графе с 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