Вычисление частных определителей

Формулы для частных определителей d_l могут также быть сформированы с использованием полных и усеченных формул i-х групп.

Первоначально необходимо для выделенного l-го пути определить множество контуров {М_l}, касающихся с l-м путем, в которое включаются номера этих контуров, число которых k_l не больше общего числа контуров, и определить контур с максимальным порядковым номером kО[1, n].

Если i > k и , то используется усеченная формула, которая получается из полной формулы путем удаления всех контуров, касающихся l-го пути. То есть

(8.6)

Алгоритмизация выражения (8.6) осуществляется следующим образом.

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

(8.7)

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

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

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

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

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

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