Определения

Каркасное дерево 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, равное размеру пространства циклов.

2 Определения .8. Обход графа

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

Наиболее общие алгоритмы обхода графов:

• Обход в глубину (Deph-First Search – DFS);

• Обход в ширину (Breadth-First Search – BFS).

2 Определения .8.1..Обход в глубину (dsf)

Обход в глубину является алгоритмом систематического посещения (прохождения) вершин графа, состоящего из двух движений:

• вперед (к еще непосещенной вершине) всегда, когда это возможно;

• возврат от текущей вершины по пройденному ребру назад (к ранее пройденной вершине), если движение вперед от текущей вершины невозможно.

После завершения обхода в глубину все ребра связанного графа оказываются разбитыми на два класса:

• ребра дерева, по которым осуществлялись впереходы из посещенных вершин в непосещенные;

• ребра касания, замыкающие циклы графа.

Частичный граф, порожденный ребрами дерева, называется деревом обхода в глубину. Этот граф является каркасным графом исходного графа.

Введем три основных атрибута алгоритма DFS:

1) Раскрашивание вершин. При выполнении алгоритма DFS вершины раскрашиваются в зависимости состояния вершины.

Раскрашивание вершин – это своебразная память (похоже на расбрасывание крошек хлеба в лабиринте – по ним можно определить местоположение в лабиринте).

2) Поддержка времени. Каждая вершина u имеет два времени: время обнаружения d[u] и время завершения f[u]. Время обнаружения соответствует моменту изменения белого цвета на серый, а время завершения – изменению серого цвета на черный. Время начинается с 1 , и с каждой отметкой события (обнаружение или завершение) время увеличивается на единицу.

3) Вершины-предшественники и DFS-дерево. Для каждой пройденной вершины в специальный массив записывается вершина-предшественник: p[u]=v. Это позволяет организовать обратное движение алгоритма.

Каждый связанный компонент графа может быть превращен в дерево удалением некоторых ребер. Каждая вершена u в дереве будет иметь указатель на своего предшественника (родителя) p[u], создавая таким образом дерево предшественник-указатель.