1.3. Деревья и циклы

1.3.1. Определение и свойства деревьев

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

Пример 1.16

Граф G₁ является деревом (рис. 1.19). Граф G₂ является лесом (рис. 1.19), он содержит три связные компоненты, каждая из которых является деревом.

Следующие утверждения эквивалентны:

• граф G есть дерево;

• граф G является связным и не имеет простых циклов;

• граф G является связным и число его ребер ровно на единицу меньше числа вершин;

• любые две различные вершины графа G можно соединить единственной (и притом простой) цепью;

• граф G не содержит циклов, но, добавляя к нему любое новое ребро, получаем ровно один (с точностью до направления обхода и начальной вершины обхода) и притом простой цикл (проходящий через добавляемое ребро).

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

Утверждение. Пусть G – дерево. Тогда любая цепь в G будет простой.

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

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

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

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

Замечание. Понятие остовного дерева и цикломатического числа аналогичным образом определяется и для произвольного связного псевдографаG.

Покажем существование остовного дерева для произвольного связного псевдографа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V, смежную в G с некоторой вершиной u_j графа G_i, и новое ребро (u_i+1, u_j) (в силу связности G и того обстоятельства, что i<n, указанная вершина u_i+1 обязательно найдется). Согласно утверждению граф G_i+1 также является деревом. Присваиваем i:=i+1 и переходим к шагу 2.

Пример 1.17.

Используя алгоритм, выделим остовное дерево графа G, изображенного на рисунке 1.20.

Решение. На рисунке 1.21 приведена последовательность графов Gi, i=1, 2, 3, 4, 5, получаемых в результате выполнения алгоритма.

При этом в силу того, что n(G)=5, G₅ - остовное дерево графа G.

Замечание. Остовное дерево связного графа может быть выделено, вообще говоря, не единственным способом.

Общее число остовных деревьев связного графа может оказаться весьма большим. Например, для полного графа с n вершинами оно равно n^n-2.

В общем случае обозначим через G произвольный граф с n вершинами, m ребрами и k компонентами. Как уже было сказано, применяя выше описанный алгоритм, получим в результате граф, являющийся остовным лесом.

Определение1.59. Число ребер, удаленных при построении остовного леса произвольного графа G, называется цикломатическим числом (или цикломатическим рангом) графа G и обозначается через  (G) = m – n + k.

Пример 1.18.

Циклический ранг дерева равен нулю, а циклический ранг циклического графа равен единице.

Определение1.60. Коциклическим рангом графа G называется число ребер в его остовном дереве.

С понятием остовного лесаТ графа G тесно связано понятие фундаментальной системы циклов, ассоциированной с Т.

Определение1.61. Если добавить к Т любое не содержащиеся в нем ребро графа G, то получим единственный цикл; множество всех циклов, получаемых таким способом (т.е. путем добавления по отдельности каждого ребра из G, не содержащегося в Т), называется фундаментальной системой циклов, ассоциированной с Т.

1.3.3. Минимальные остовные деревья нагруженных графов

Пусть теперь каждому ребру xXсвязного графа G=(V,X) c непустым множеством ребер Х поставлена в соответствие величина l(x) – длина ребра х, т.е. граф G является нагруженным. Приведем алгоритм, позволяющий найти остовное дерево графа G с минимальной суммой длин содержащихся в нем ребер (по сравнению со всеми другими остовными деревьями графа G).

Определение1.62. Остовное дерево связного нагруженного граф G с минимальной суммой длин содержащихся в нем ребер будем называть минимальным остовным деревом (МОД) графа G.

Алгоритм выделения МОД нагруженного связного графа G:

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

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

Шаг 3. Строим граф G_i+1, добавляя к графу G_i новое ребро минимальной длины, выбранное среди всех ребер графа G, каждое из которых инцидентно к какой-нибудь вершине графа G_i и одновременно инцидентно какой-нибудь вершине графа G, не содержащейся в G_i. Вместе с этим ребром включаем в G_i+1 и инцидентные ему вершины, не содержащуюся в G_i. Присваиваем i:=i+1 и переходим к шагу 2.

Пример 1.19.

Определить МОД нагруженного графа G, изображенного на рисунке 1.22, используя алгоритм.

Решение. На рисунке 1.23 приведена последовательность графов Gi, i=2,3,4,5, получаемых в результате выполнения алгоритма. При этом в силу того, что n(G)=5, G5 - МОД графа G. Причем, МОД(G) = 7.

Замечание. Возможно выделить в графе несколько остовных деревьев, каждое из которых будет являться минимальным, при этом величина МОД для всех этих деревьев будет равной.

Замечание. Для выделения МОД нагруженного псевдографаG следует предварительно удалить из G петли, из кратных ребер оставить лишь ребра минимальной длины.