Полные графы и деревья
Граф называется полным, если любые две его вершины смежены, т.е. имеют общее ребро.
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
Пусть дан полный граф. Ребрам приписаны штрафы. На основе этого графа строят дерево, имеющее минимальный суммарный штраф.
Для этого на каждом шаге выбирают ребро, имеющее минимальный штраф и не образующее цикл с уже выбранными ребрами.
.
Пример.
2 3 5 5
6
4 4 8 6
6
Жирными линиями выделено минимальное дерево
Теорема Кэлидля раскрашенных деревьев.
Для n вершин существует nn-2 различных помеченных деревьев.
Например, существует 16 различных деревьев с четырьмя вершинами.
1 2 3 4
4 3 2 1
4 вершины Þ 44 - 2 = 16 различных помеченных деревьев
1 2 3