Деревья

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

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

1

5 2

- К₅

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

Дерево - это связный граф без циклов. Можно дать другое определение дерева или вывести его из первого. Дерево – это граф, между любой парой вершин которого существует единственная цепь.

Теорема: В графе типа дерева с n вершинами n-1 ребер.

Доказательство. Для графа, состоящего лишь из одной вершины, это соотношение выполняется. Пусть оно выполняется и для графа с n-1 вершинами, тогда добавление новой дуги приводит к добавлению и одной вершины, что сохраняет соотношение.

Примеры деревьев.

Лесом называется граф, состоящий из нескольких компонент связности, каждая из которых является деревом.

Диаметром для графов типа дерева является максимальное расстояние между его вершинами.

. Определим для каждой вершины ее расстояние от самого удаленного листа Минимальное число - радиус, эта вершина корневая (центральная).

В любом дереве существует одна или две (смежные) корневые вершины

4 4

2 3

-Диаметр 4.

3 3 4 4

4 3 3 4

Диаметр: 5

Радиус : 3

5 5 4 4 4 4 5 5