Алгоритм построения произвольного остова

Рассмотрим словесное описание алгоритма:

1. Для каждой компоненты i графа выполняем пункты 2 и 3.

2. Строим частичный подграф, содержащий все n_i вершин i-й компоненты и не содержащий ребер (0- граф).

3. Если в текущий частичный граф включены уже n_i -1ребер, то остов для компоненты i построен, иначе выбираем очередное ребро компоненты и пытаемся его включить в текущий граф.

Если в текущем графе это не приводит к образованию цикла, то включаем ребро, иначе - не включаем. Ребро считаем рассмотренным. Выполняем п. 3.

Пример 3.10.

Рис. 3.10

Так как цикл не образовался, то все рёбра с номерами 1, 2, 3, 4 включены в остов. Проверяем по (3.3): m= 4, n= 5и4=5-1.

Алгоритм построения минимального остова

Для взвешенного графа остов с наименьшей суммой весов для вошедших в него рёбер называется минимальным (кратчайшее связное дерево). Если в сформулированном ранее алгоритме построения обычного остова рассматривать рёбра в порядке возрастания их весов, то будет построен минимальный остов.

Пример 3.11.

Рис.3.11