Деревья. Дерево - это связный граф без циклов

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

Теорема: В графе типа дерева с 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