Точный алгоритм нахождения

каркасного дерева графа

При любом исполнении алгоритма поиска в глубину (DFS) изменение цвета вершин идет вдоль каркасного дерева, следовательно запись порядка прохождения вершин вDFSдаст запись каркасного дерева (см.п.1.8.).

Простые алгоритма нажодения каркасного дерева

Э

Алгоритм возведения

ти алгоритмы применимы лишь для графов совсем небольших размеров из-за трудностей нахождения циклов.

1. Выбирать ребра графа один за другим так, чтобы не создавать циклов.

2. Повторять 1 до тех пор, пока в дерево не будут включены все вершины.

Алгоритм вырезания

Выбрать любой цикл в неграфе и удалить одно ребро.

Повторять 1 до тех пор, пока в графе не останется циклов.

Определения

Каркасное дерево T=(V,E¹) связного простого графаG=(V,E), |V|=n, |E|=m, содержитn-1 ребро. Каждое ребро, не принадлежащее каркасному деревуT=(V,E¹), порождает в точности один цикл при добавлении его кT. Такой цикл является элементоммножества фундаментальных циклов графа G относительно каркасного дерева T.

Поскольку каркасное дерево имеет n-1 ребро, в фундаментальном множестве циклов графаGотносительно каркасного дереваTимеетсяm-n=1 циклов (|V|=n, |E|=m).

Определения

Если ребра графа Gобозначеныe₁,e₂,…,e_m, а фундаментальные циклы – Σ_i,i=1,2,…,k, то элементыматрицы фундаментальных циклов С=(с_ij)_kxmопределяются следующим образом:

1, если Σ_iсодержит реброe_j

c_{ij =}

0 в остальных случаях

Пример

Множество фундаментальных

циклов

Σ₁= {e₁,e₅,e₆,e₈}

Σ₂ = {e₂,e₇,e₈}

Σ₃= {e₂,e₃,e₉}

Σ₄= {e₁,e₃,e₄}

Каркасное дерево T

μ = 9-6+1= 4

Рис.2.7.6. ГрафGи его матрица фундаментальных циклов

Определения

Пространством циклов называется множество всех простых циклов графаG. Множество фундаментальных циклов неоргафаGотносительно каркасного дереваTобразуетбазиспространства циклов.

Это означает, что все другие циклы графа G могут быть получены линейной комбинацией (операцией по модулю 2 – mod₂) фундаментальных циклов графа G относительно каркасного дерева T.

Меры

• μ - цикломатическое числографаG, равное размеру пространства циклов.