Конструирование разомкнутых алгебраических матрично-структурных моделей требует решения проблемы формирования символьно-численных соотношений между любыми узлами графа произвольной сложности, представленного в виде структурной матрицы S.
Предлагаемый алгоритм автоматического формирования дерева вычислений основан на использовании алгоритма конструирования универсальной топологической формулы Мейсона [9] с помощью формул групп некасающихся контуров n-го порядка.
Компьютерная реализация универсальной топологической формулы Мейсона
(8.1)
позволяющая определить коэффициент передачи или передаточную функцию Hgy между любыми заданными узлами g, y графа, требует алгоритмизации задач вычисления главного D и частных dl определителей графа. Решению этих задач предшествует исследование топологии графа на предмет поиска комбинаций некасающихся контуров и прямых путей. Последнее в большинстве случаев выполняется путем полного перебора по узлам сравниваемых контуров. Попытаемся избежать этой длительной операции.
Если применить формулы групп некасающихся контуров n-го порядка, можно значительно упростить процедуру вычисления главного определителя D.
Группой с i-ым контуром или просто i-ой группой называется часть определителя графа, содержащая все некасающиеся сочетания с i-ым контуром первого порядка (все контуры n-го порядка для n=1, 2,..., в состав которых входит контур i-го порядка).
Формула для i-ой группы записывается в следующем виде
(8.2)
Первоначально рассмотрим алгоритмы решения отдельных задач.
Исследование известных алгоритмов идентификации контуров графа показало, что при задании графа в виде структурной матрицы S наиболее рациональным является алгоритм "построения прадерева с корнем" [9].
Для реализации этого алгоритма будем использовать модифицированную матрицу смежности M [9]. Для структурной матрицы S1, внутренними элементами sji которой являются числовые коды ветвей графа, соответствующие, как правило, номерам передач этих ветвей, то можно утверждать, что
(8.3)
то есть модифицированная матрица смежности M получается путем транспонирования структурной матрицы S1 и последующего обнуления диагональных элементов квадратной части матрицы M.
Для пояснения всех нижеизложенных алгоритмов будем использовать абстрактный граф, схема и МСП которого приведены на рис. 8.1.
С помощью выражения (8.3) получим модифицированную матрицу смежности M (рис. 8.2)
Теперь рассмотрим основные этапы идентификации контуров.
В результате получим прадерево с корнем, анализ которого позволит легко идентифицировать все контуры графа.
Фрагмент прадерева для узла 1 представлено на рис. 8.3 Непосредственный его анализ позволяет выделить три контура k1, k2, k3, связанных с узлом 1. Дальнейшие удаления из прадерева ветвей, инцидентных с узлами 1, 2, 3, ... позволяет выделить остальные контуры графа k4, k5, k6.
Результаты поиска контуров записываем в таблицу идентификации контуров и матрицу контуров на узлах графа Z, которые для нашего примера имеют вид:
Строки матрицы контуров на узлах графа соответствуют номерам контуров, а столбцы - номерам узлов.
Нетрудно заметить, что для идентификации контуров графа целесообразно использовать лишь квадратную часть модифицированной матрицы смежности.
Для выполнения процесса поиска путей нужно задать начальный xn и конечный xk узлы пути. В процессе идентификации путей сначала проводится сравнение j-го текущего узла с k-ым конечным узлом графа. Путь будет идентифицирован, если выполняется условие j=k.
Результаты поиска путей записываем в таблицу идентификации путей и матрицу путей на узлах графа T, которые для нашего примера имеют вид
Для формирования групп контуров графа первоначально необходимо определить пары некасающихся контуров. Очень часто принято результаты идентификации пар некасающихся контуров представлять в виде матрицы касаний контуров по два F2 [9]. Здесь строками и столбцами являются кодовые номера контуров графа. Если i-й контур графа имеют одну или более общих вершин с j-м контуром, т.е. являются касающимися, то элемент матрицы fij=1. В противном случае - fij=0.
Нужно заметить, что матрица F2 симметричная. Поэтому для получения информации о парах некасающихся контуров достаточно использовать лишь ее верхнюю или нижнюю треугольные части.
Матрица F2 определяется с помощью булева произведения матрицы Z на результат ее транспонирования Zт, то есть
(8.4)
Для нашего примера верхняя треугольная часть имеет вид
Чтобы сформировать формулу i-й группы осуществляется последовательный обход матрицы от i-й до последней строки, в ходе которого путем поиска нулевых элементов матрицы выполняется построение дерева сочетаний некасающихся с i-м контуром контуров графа. Обход последнего дерева позволит сформировать формулы i-й группы Di.
На рис. 8.4 представлены деревья сочетаний некасающихся контуров и формулы всех групп контуров.
При известных формулах всех n-групп контуров определитель графа вычисляется с помощью выражения
(8.5)
Алгоритмизация выражения (8.5) осуществляется последовательным наращиванием формулы на каждом этапе формирования i-й группы.
Формулы для частных определителей dl могут также быть сформированы с использованием полных и усеченных формул i-х групп.
Первоначально необходимо для выделенного l-го пути определить множество контуров {Мl}, касающихся с l-м путем, в которое включаются номера этих контуров, число которых kl не больше общего числа контуров, и определить контур с максимальным порядковым номером kО[1, n].
Если i > k и , то используется усеченная формула, которая получается из полной формулы путем удаления всех контуров, касающихся l-го пути. То есть
(8.6)
Алгоритмизация выражения (8.6) осуществляется следующим образом.
(8.7)
Матрица касания прямых путей Tk от внешних узлов к вершине l с контурами исходного графа (рис. 8.1) и множество {Мl} имеют вид:
Тогда частные определители dl, (l=1, 2, 3, 4) формируются следующим образом:
Когда определены прямые пути передачи внешних сигналов к узлу l и построены формулы вычисления главного и частных определителей исходного графа, процесс построения дерева вычислений представляет собой последовательность следующих действий.
Выполнение указанной последовательности действий приведет к преобразованию исходного графа (рис.8.1) в дерево, представленное на рис. 8.5.