5.4 Деревья и циклы

Определение. Граф G называется деревом, если он является связным и не имеет циклов. Граф G, все компоненты связности которого являются деревьями, называется лесом.

У графа, который является деревом, число ребер на единицу меньше числа вершин. Дерево не содержит циклов, любые две его вершины можно соеденить единственной простой цепью.

Если у дерева G есть, по крайней мере, одно ребро, то у него обязательно найдется висячая вершина, т.к. в противном случае в графе будет цикл.

Для графов, которые сами по себе не являются деревьями, вводится понятие остовного дерева.

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

Пусть G – связный граф. Тогда остовное дерево графа G (если оно существует) должно содержать n(G)-1 ребер.

Таким образом, любое остовное дерево графа G есть результат удаления из графа G ровно m(G) - (n(G) - 1) = m(G) – n(G) + 1 ребер.

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

Одной из самых распространенных задач является задача построения остовного дерева минимальной длины графа. Для решения этой задачи применяется следующий алгоритм.

1) Выберем в графе G ребро минимальной длины. Вместе с инциндентными ему вершинами оно образует подграф G₂.

2) Строим граф G₃, добавляя к графу G₂ новое ребро минимальной длины, выбранное среди ребер графа G₂, каждое из которых инциндентно какой-либо вершине графа G₂, и одновременно инциндентно какой – либо вершине графа G, не содержащейся в графе G₂.

3) Строим графы G₄, G₅, …,n , повторяя действия пункта 2 до тех пор, пока не переберем все вершины графа G.