Исследование известных алгоритмов идентификации контуров графа показало, что при задании графа в виде структурной матрицы Sнаиболее рациональным является алгоритм "построения прадерева с корнем" [9].
Для реализации этого алгоритма будем использовать модифицированную матрицу смежности M [9]. Для структурной матрицы S1, внутренними элементами sji которой являются числовые коды ветвей графа, соответствующие, как правило, номерам передач этих ветвей, то можно утверждать, что
(8.3)
то есть модифицированная матрица смежности M получается путем транспонирования структурной матрицы S1 и последующего обнуления диагональных элементов квадратной части матрицы M.
Для пояснения всех нижеизложенных алгоритмов будем использовать абстрактный граф, схема и МСП которого приведены на рис. 8.1.
С помощью выражения (8.3) получим модифицированную матрицу смежности M (рис. 8.2)
Теперь рассмотрим основные этапы идентификации контуров.
Последовательно, начиная с первой строки (i=1), осуществляем просмотр элементов матрицы M до встречи с элементом mij№0.
Переходим к j-ой строке матрицы M, указанной ее элементом не равным нулю mij№0.
Номера строк i, и столбцов j, соответствующие номерам узлов истока и стока ветви графа, и код этой ветви записываем в специальный блок цифровой информации. Эта операция соответствует последовательному вычерчиванию ветвей дерева, начинающегося с узла i.
Повторяем выполнение пунктов 1-3 до тех пор, пока не будут определены все возможные пути из узла i в узел i и построены все возможные тупиковые ветви.
Повторяем выполнение пунктов 1-4 для всех узлов исходного графа (i=2, 3, ... ), после вычеркивания из матрицы M (i-1) строки.
В результате получим прадерево с корнем, анализ которого позволит легко идентифицировать все контуры графа.
Фрагмент прадерева для узла 1 представлено на рис. 8.3 Непосредственный его анализ позволяет выделить три контура k1, k2, k3, связанных с узлом 1. Дальнейшие удаления из прадерева ветвей, инцидентных с узлами 1, 2, 3, ... позволяет выделить остальные контуры графа k4, k5, k6.
Результаты поиска контуров записываем в таблицу идентификации контуров и матрицу контуров на узлах графа Z, которые для нашего примера имеют вид:
Строки матрицы контуров на узлах графа соответствуют номерам контуров, а столбцы - номерам узлов.
Нетрудно заметить, что для идентификации контуров графа целесообразно использовать лишь квадратную часть модифицированной матрицы смежности.
Для выполнения процесса поиска путей нужно задать начальный xn и конечный xk узлы пути. В процессе идентификации путей сначала проводится сравнение j-го текущего узла с k-ым конечным узлом графа. Путь будет идентифицирован, если выполняется условиеj=k.
Результаты поиска путей записываем в таблицу идентификации путей и матрицу путей на узлах графа T, которые для нашего примера имеют вид