Универсальный алгоритм автоматического построения дерева вычислений в задачах конструирования вычислительных моделей

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

Предлагаемый алгоритм автоматического формирования дерева вычислений основан на использовании алгоритма конструирования универсальной топологической формулы Мейсона [9] с помощью формул групп некасающихся контуров n-го порядка.

Компьютерная реализация универсальной топологической формулы Мейсона

(8.1)

позволяющая определить коэффициент передачи или передаточную функцию Hgy между любыми заданными узлами g, y графа, требует алгоритмизации задач вычисления главного D и частных dl определителей графа. Решению этих задач предшествует исследование топологии графа на предмет поиска комбинаций некасающихся контуров и прямых путей. Последнее в большинстве случаев выполняется путем полного перебора по узлам сравниваемых контуров. Попытаемся избежать этой длительной операции.

Если применить формулы групп некасающихся контуров n-го порядка, можно значительно упростить процедуру вычисления главного определителя D.

Группой с i-ым контуром или просто i-ой группой называется часть определителя графа, содержащая все некасающиеся сочетания с i-ым контуром первого порядка (все контуры n-го порядка для n=1, 2,..., в состав которых входит контур i-го порядка).

Формула для i-ой группы записывается в следующем виде

Di= -ki(1- ki+1(1- ki+2(...)-ki+m)- ki+2(1- ki+3(...)- ki+m)- ...- ki+m)

(8.2)

Первоначально рассмотрим алгоритмы решения отдельных задач.

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

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

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

(8.3)

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

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

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


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

  1. Последовательно, начиная с первой строки (i=1), осуществляем просмотр элементов матрицы M до встречи с элементом mij0.
  2. Переходим к j-ой строке матрицы M, указанной ее элементом не равным нулю mij0.
  3. Номера строк i, и столбцов j, соответствующие номерам узлов истока и стока ветви графа, и код этой ветви записываем в специальный блок цифровой информации. Эта операция соответствует последовательному вычерчиванию ветвей дерева, начинающегося с узла i.
  4. Повторяем выполнение пунктов 1-3 до тех пор, пока не будут определены все возможные пути из узла i в узел i и построены все возможные тупиковые ветви.
  5. Повторяем выполнение пунктов 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, которые для нашего примера имеют вид

Формирование групп и определителя графа

Для формирования групп контуров графа первоначально необходимо определить пары некасающихся контуров. Очень часто принято результаты идентификации пар некасающихся контуров представлять в виде матрицы касаний контуров по два 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) осуществляется следующим образом.

  1. Путем вычисления булева произведения матрицы путей на узлах графа T на транспортированную матрицу контуров на узлах ZT формируем матрицу касаний путей с контурами Tk, т. е.

    (8.7)

  2. Последовательно просматривая l-ю строку матрицы Tk, формируем множество контуров, касающихся с l-м путем {Мl}, каждый элемент которого является номером столбца j матрицы E при elj = 0.
  3. Конструируются формулы полных и усеченных групп и вычисляют частный определитель dl, согласно выражению (8.6).
  4. Пункты 2, 3 выполняются для всех контуров исходного графа.

Матрица касания прямых путей Tk от внешних узлов к вершине l с контурами исходного графа (рис. 8.1) и множество {Мl} имеют вид:

Тогда частные определители dl, (l=1, 2, 3, 4) формируются следующим образом:

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

  1. Конструирование формулы вычисления передач внешних сигналов к первоначально выбранному узлу x графа Q1, Q2, ..., Qr, где r - число внешних сигналов.
  2. Упрощение исходного графа путем исключения из него ветвей, входящих в узел x, перевод узла в группу внешних сигналов.
  3. Последовательное приведение графа к дереву вычислений путем конструирования формул передач внешних и, переведенных во внешние, сигналов к выбранным узлам графа.

Выполнение указанной последовательности действий приведет к преобразованию исходного графа (рис.8.1) в дерево, представленное на рис. 8.5.

Рейтинг@Mail.ru