Деревья и древовидности

Частным случаем связных сетей являются деревья.

Лес — неориентированный граф без циклов. Компонентами связности леса являются деревья.

Дерево G ₁ сети G, это связный подграф G, не содержащий циклов.

Подграф является деревом, если выполнены любые два из трех следующих условий:

1. Подграф связный.

2. Подграф ациклический.

3. Число дуг подграфа меньше числа его вершин на единицу.

Для любых двух узлов дерева существует единственный путь между ними. Остовным деревом (остовом) сети называют дерево, содержащее все узлы исходной сети. Таким образом, G _o = {N, A _o } - остовное дерево G = {N, A}, если A _oc A и G _o - дерево.

Весом дерева в сети, для дуг которой определена обобщенная стоимость c_ij, называют сумму с_ij по всем дугам дерева.

Кратчайшим остовом называют остов с наименьшим для всех остовов данной сети весом.

Максимальным остовом называют остов с наибольшим для всех остовов данной сети весом.

Древовидностью называют дерево, состоящее только из ориентированных дуг и имеющее единственный корень - узел, из которого дуги только исходят.

Древовидное дерево - дерево, являющееся древовидностью.

Древовидный остов, являющийся древовидностью.

Примеры дерева, остова, древовидности, древовидного остова приведены на рис. 5.

Алгоритм определения остовного дерева для произвольного связного псевдографа G=(V,X)

Шаг 1. Выбираем в G произвольную вершину u₁, которая образует подграф G₁ псевдографа G, являющийся деревом. Полагаем i=1.

Шаг 2. Если i=n, где n=n(G), то задача решена, и G_i – искомое остовное дерево псевдографа G. В противном случае переходим к шагу 3.

Шаг 3. Пусть уже построено дерево G_i, являющееся подграфом псевдографа G и содержащий некоторые вершины u₁, …, u_i, где 1<i < n-1. Строим граф G_i+1, добавляя к графу G_i новую вершину u_i+1, смежную в G с некоторой вершиной u_j графа G_i, и новое ребро (u_i+1, u_j) (в силу связности G и того обстоятельства, что i < n, указанная вершина u_i+1 обязательно найдется). Согласно утверждению граф G_i+1 также является деревом. Присваиваем i:=i+1 и переходим к шагу 2.