Поиск контуров и путей графа

Исследование известных алгоритмов идентификации контуров графа показало, что при задании графа в виде структурной матрицы Sнаиболее рациональным является алгоритм "построения прадерева с корнем" [9].

Для реализации этого алгоритма будем использовать модифицированную матрицу смежности M [9]. Для структурной матрицы S₁, внутренними элементами s_ji которой являются числовые коды ветвей графа, соответствующие, как правило, номерам передач этих ветвей, то можно утверждать, что

(8.3)

то есть модифицированная матрица смежности M получается путем транспонирования структурной матрицы S₁ и последующего обнуления диагональных элементов квадратной части матрицы M.

Для пояснения всех нижеизложенных алгоритмов будем использовать абстрактный граф, схема и МСП которого приведены на рис. 8.1.

С помощью выражения (8.3) получим модифицированную матрицу смежности M (рис. 8.2)

Теперь рассмотрим основные этапы идентификации контуров.

1. Последовательно, начиная с первой строки (i=1), осуществляем просмотр элементов матрицы M до встречи с элементом m_ij№0.
2. Переходим к j-ой строке матрицы M, указанной ее элементом не равным нулю m_ij№0.
3. Номера строк i, и столбцов j, соответствующие номерам узлов истока и стока ветви графа, и код этой ветви записываем в специальный блок цифровой информации. Эта операция соответствует последовательному вычерчиванию ветвей дерева, начинающегося с узла i.
4. Повторяем выполнение пунктов 1-3 до тех пор, пока не будут определены все возможные пути из узла i в узел i и построены все возможные тупиковые ветви.
5. Повторяем выполнение пунктов 1-4 для всех узлов исходного графа (i=2, 3, ... ), после вычеркивания из матрицы M (i-1) строки.

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

Фрагмент прадерева для узла 1 представлено на рис. 8.3 Непосредственный его анализ позволяет выделить три контура k₁, k₂, k₃, связанных с узлом 1. Дальнейшие удаления из прадерева ветвей, инцидентных с узлами 1, 2, 3, ... позволяет выделить остальные контуры графа k₄, k₅, k₆.

Результаты поиска контуров записываем в таблицу идентификации контуров и матрицу контуров на узлах графа Z, которые для нашего примера имеют вид:

Строки матрицы контуров на узлах графа соответствуют номерам контуров, а столбцы - номерам узлов.

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

Для выполнения процесса поиска путей нужно задать начальный x_n и конечный x_k узлы пути. В процессе идентификации путей сначала проводится сравнение j-го текущего узла с k-ым конечным узлом графа. Путь будет идентифицирован, если выполняется условиеj=k.

Результаты поиска путей записываем в таблицу идентификации путей и матрицу путей на узлах графа T, которые для нашего примера имеют вид