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

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

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

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

(8.1)

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

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

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

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

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

(8.2)

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