Полные графы

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

1

5 2

- К₅

4 3

Теорема: В полном графе с n вершинами есть n(n-1)/2 ребер.

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

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

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

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

1 2 1 2

G G̅

4 3 4 3

1 1

5 2 5 2

G G̅

4 3 4 3