Остовное дерево связного графа.

Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом. Любое остовное дерево графа G есть результат удаления из G ровно m (G) – (n (G) –1) = m (G) – n (G) + 1 рёбер.

Число m (G) – n (G) + 1 называется цикломатическим числом связного графа G и обозначается через v (G).

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

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

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

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