ON SOME ALGORITHMS FOR THE ANALYSIS OF COMPLEX SYSTEMS

E. I. Tsimbalist, L. A. Naumov

(Presented by the scientific seminar of the Department of Radio Engineering)

By the present time a number of effective methods have been developed for the analysis of electronic circuits, involving the performance, in a definite sequence, of formal operations on the matrix or graph of the circuit under study [1–3, etc.]. Thus, for example, a widely known method of analysis of complex electrical networks with reversible and irreversible components is based on the method of generalized numbers; it is distinguished by a minimal amount of necessary computations and is suitable both for manual calculations and for digital computers [2].

Below we propose algorithms that formalize the writing of Mason’s formula for systems represented by a signal graph or by an adjacency matrix.

Let there be a system containing \(n\) vertices connected with one another by a set of directed arcs \(r_{ij}\), which can be represented by the adjacency matrix of the graph \(\vec{L}\) [4]. It is convenient to write this matrix in the following form:

\[ R = [r_{ij}], \]

where

\[ \begin{cases} r_{ij} = ij, & \text{if there is transmission from } i \text{ to } j,\\ r_{ij} = 0, & \text{if there is no transmission from } i \text{ to } j. \end{cases} \]

Thus, in any row of the matrix \(R\) there are all arcs for which the given vertex is the source, i.e., the outgoing half-stars, and in a column there are arcs for which this same vertex is the sink (the incoming half-stars).

We pose the problem:

1. Find the additive disturbance (the output signal \(v_j\)).
2. Determine the sensitivity of the graph transmission \(T_{ij}\) to changes in the transmission of any branch [5]

\[ S_T = \frac{\partial T_{ij}}{\partial r_{ab}} = T_{ia}\cdot T_{bj}, \tag{1} \]

where

\[ T_{ij}=\frac{1}{\Delta}\sum_k p_k \Delta_k \quad \text{— the transmission of the graph from } i \text{ to } j, \tag{2} \]

\[ p_k \text{ — the transmission of the } k\text{-th path from } i \text{ to } j, \]

\[ \Delta_k \text{ — the algebraic cofactor of the } k\text{-th path,} \]

\[ \Delta = 1 - \sum_q L_q^{(1)} + \sum_q L_q^{(2)} - \sum_q L_q^{(3)} + \ldots,\quad \text{and} \]

$L_q^{(p)}$ is the product of the $q$-th possible combination of $p$ nonintersecting contours.

If for simple systems the use of (1), (2) causes no difficulties, then for sufficiently complex ones with a large number of cross-connections, the computation of $T_{ij}$ directly from examination of the graph does not give a complete guarantee that all transmissions and contours have been found. The problem posed can be solved by raising the adjacency matrix $[R]$ to the $n$-th power and carrying out certain logical operations. All necessary components of (1), (2) will be found in the elements $(i\ldots j)_\Sigma$, $(i\ldots i)_\Sigma$ of the summary matrix

\[ [R]_\Sigma=\sum_{m=1}^{t=n}[R]^m, \]

where

\[ (i\ldots j)_\Sigma=\sum_{m=1}^{n-1}(i\ldots j)_m;\qquad (i\ldots i)_\Sigma=\sum_{m=2}^{n}(i\ldots i)_m. \]

This algorithm is easily programmed, but it is redundant and therefore heavily loads the RAM of the computer.

The indicated difficulties can be overcome to a considerable extent if set-theoretic methods of analysis are brought in, using the symbolism of set theory and performing operations over the field of modulus 2. Then, in order to find (1), (2), i.e., all contours and paths between vertices, the following algorithm can be used:

1. On the basis of the graph or its adjacency matrix, a table of outgoing half-stars is compiled, formed by the sets of arcs leaving the $m$-th vertex of the graph

\[ \beta_m(m/l)= \begin{array}{c} 1\\ 2\\ \cdot\\ n \end{array} \left[ \begin{array}{ccccc} 1&2&\cdot&\cdot& n\\ 1&2&\cdot&\cdot& n\\ \cdot&\cdot&\cdot&\cdot&\cdot\\ 1&2&\cdot&\cdot& n \end{array} \right], \tag{3} \]

where $l=\{1,2,\ldots,n\}$ is the set of vertices at which the arcs leaving $m$ terminate.

1. From $\beta_m(m/l)$ the main diagonal is cleared, i.e., the simplest contours—loops around the $m$-th vertex—are excluded (and stored). As a result one obtains a table of outgoing half-stars of the subgraph without loops, which is conveniently written in the form of a correspondence of the $m$-th vertex to a set of vertices $l_m$.

\[ \begin{array}{c} 1\,—\,l_1\\ 2\,—\,l_2\\ \cdots\\ m\,—\,l_m\\ \cdots\\ n\,—\,l_n \end{array} \tag{3'} \]

Naturally, in (3) or (3′) there is information about all one-step paths.

1. For any element of (3) or (3′) beginning with $m=i$, a scalar-vector product is formed (the latter is performed over the field of modulus 2), i.e., a set of new numbers of the form

\[ \beta\left(m/\left[\frac{l_m}{l_m}\right]_2\right). \tag{4} \]

In (4) all two-step paths and contours obtained when \(m\) coincides with the \(i\)-th element of the set \(l_m\) are found; these are stored and deleted from subsequent operations.

1. For each element of (4), the operation described above is repeated, with the only difference that \(m'\) (and hence \(l'_{m}\)) corresponds to the last index \(v=m'\) of the preceding number, and the vector product is taken only with \(v\). After eliminating duplications in finding the vector product and storing the three-step contours (they are also deleted), the algorithm continues until all \(n-1\) paths and contours have been found. In carrying out the \(n\)-th operation, only the \(m\) in \(l'_m\) that corresponds to the Hamiltonian contour (if it exists) is taken into account.

Fig. 1

Let us consider the finding of all paths and contours by the algorithm proposed above on an example.

Example 1. Consider the signal graph (Fig. 1), isomorphic to a certain physical structure, and for it compose the table of outcome semi-stars in the form (3) and (3′)

\[ \beta_m(m_i l)= \begin{array}{c|cccccc} 1 & - & 234 & - & 6 \\ 2 & 1 & - & 3 & - & - & - \\ 3 & - & 2 & - & 4 & - & - \\ 4 & - & 2 & - & - & - & - \\ 5 & - & - & 34 & - & - & 6 \\ 6 & 1 & - & - & 4 & 5 & - \end{array} \tag{3} \]

\[ \begin{array}{l} 1-2346\\ 2-13\\ 3-24\\ 4-2\\ 5-346\\ 6-145 \end{array} \tag{3′} \]

1. We write out the one-step paths: 12, 13, 14, 16, 21, 23, 32, 34, 42, 53, 54, 56, 61, 64, 65.

2. We determine the two-step paths and contours:

\[ 1 \times \left[ \begin{array}{cccc} 2 & 3 & 4 & 6\\ 13 & 24 & 2 & 145 \end{array} \right]_2 =121,\ 123,\ 132,\ 134,\ 142,\ 161,\ 164,\ 165; \]

\[ 2 \times \left[ \begin{array}{cc} 1 & 3\\ 2346 & 24 \end{array} \right]_2 =212,\ 213,\ 214,\ 216,\ 232,\ 234; \]

\[ 3 \times \left[ \begin{array}{cc} 2 & 4\\ 13 & 2 \end{array} \right]_2 =321,\ 323,\ 342; \]

\[ 4 \times \left[ \begin{array}{c} 2\\ 13 \end{array} \right]_2 =421,\ 423; \]

\[ 5 \times \left[ \begin{array}{ccc} 3 & 6 & 4\\ 24 & 145 & 2 \end{array} \right]_2 =532,\ 534,\ 542,\ 561,\ 564,\ 565; \]

\[ 6 \times \left[\frac{1}{2346}\ \frac{4}{2}\ \frac{5}{346}\right]_2 = 612,\ 613,\ 614,\ 616,\ 642,\ 653,\ 654,\ 656. \]

3. We find the three-link paths and contours:

\[ 1 \times \left[ 2 \times \frac{3}{24}\ 3 \times \frac{2}{13}\ 3 \times \frac{4}{2}\ 4 \times \frac{2}{13}\ 6 \times \frac{4}{2}\ 6 \times \frac{5}{346} \right]_2 = \]

\[ = 1234,\ 1321,\ 1342,\ 1421,\ 1423,\ 1642,\ 1652,\ 1654; \]

\[ 2 \times \left[ 1 \times \frac{3}{24}\ 1 \times \frac{4}{2}\ 1 \times \frac{6}{145}\ 3 \times \frac{4}{2} \right]_2 = 2132,\ 2134,\ 2142,\ 2164,\ 2165,\ 2342 \]

and so on.

4. Eliminating duplications among the contours, we obtain the set of paths \((p_k)_{ij}\) and all contours:

\[ \begin{aligned} (p_k)_{12} &= 12,\ 132,\ 142,\ 1342,\ 1642,\ 16532,\ 16542,\ 165342;\\ (p_k)_{13} &= 13,\ 123,\ 1423,\ 1653,\ 16423,\ 165423;\\ (p_k)_{14} &= 14,\ 134,\ 164,\ 1234,\ 1654,\ 16534;\\ (p_k)_{15} &= 165;\\ (p_k)_{16} &= 16;\\ (p_k)_{21} &= 21;\\ (p_k)_{23} &= 23,\ 213,\ 21653;\\ (p_k)_{24} &= 214,\ 234,\ 2134,\ 2164,\ 21654,\ 216534;\\ (p_k)_{25} &= 2165;\\ (p_k)_{26} &= 216;\\ (p_k)_{31} &= 321,\ 3421;\\ (p_k)_{32} &= 32,\ 342;\\ (p_k)_{34} &= 34,\ 3214,\ 32164,\ 321654;\\ (p_k)_{35} &= 32165,\ 342165;\\ (p_k)_{36} &= 3216,\ 34216;\\ (p_k)_{41} &= 421;\\ (p_k)_{42} &= 42;\\ (p_k)_{43} &= 423,\ 4213,\ 421653;\\ (p_k)_{45} &= 42165;\\ (p_k)_{46} &= 4216;\\ (p_k)_{51} &= 561,\ 5321,\ 5421,\ 53421;\\ (p_k)_{52} &= 532,\ 542,\ 5342,\ 5612,\ 5642,\ 56132,\ 56142,\ 561342;\\ (p_k)_{53} &= 53,\ 5423,\ 5613,\ 54213,\ 56123,\ 561423,\ 564213;\\ (p_k)_{54} &= 54,\ 534,\ 564,\ 5614,\ 53214,\ 56134,\ 532164,\ 561234;\\ (p_k)_{56} &= 56,\ 53216,\ 54216,\ 534216;\\ (p_k)_{61} &= 61,\ 6421,\ 65321,\ 65421,\ 653421;\\ (p_k)_{62} &= 612,\ 642,\ 6132,\ 6142,\ 6532,\ 6542,\ 61342,\ 65342;\\ (p_k)_{63} &= 613,\ 653,\ 6123,\ 6423,\ 61423,\ 64213,\ 65423,\ 654213; \end{aligned} \tag{5} \]

\[ (p_k)_{64}=64,\ 614,\ 651,\ 6134,\ 6531,\ 61234,\ 653214; \]

\[ (p_k)_{65}=65; \]

\[ \begin{gathered} L_1=121;\quad L_2=161,\quad L_3=232,\quad L_4=565,\quad L_5=1321,\quad L_6=1421,\quad L_7=2342,\\ L_8=13421,\quad L_9=16421,\quad L_{10}=165321,\quad L_{11}=165421,\quad L_{12}=1653421. \end{gathered} \]

The subsequent analysis, leading to (1), (2), reduces to finding contours that are in contact with one another and with the selected \((P_k)_{ij}\). The criterion of contact is the presence of at least one common index.

When carrying out the computations, it proves useful to represent the graph \(\vec L\) itself as an ordinary graph \(L\), whose vertices are the contours of \(\vec L\), and an edge between the \(i\)-th and \(j\)-th vertices of \(L\) exists only when the two indicated contours do not touch. Then \(L_q^{(2)}\) is determined by the product of the indices of mutually incident vertices, \(L_q^{(3)}\) by the product of the indices of the vertices of complete three-vertex subgraphs of \(L\), etc. (Fig. 2).

From Fig. 2 it is seen that \(L_q^{(a)}=0\) for \(a\geqslant 3\) (since there are no complete \(a\geqslant 3\)-vertex subgraphs).

Then

\[ \Delta = 1-\sum_{q=1}^{12} L_q + L_4(L_1+L_3+L_5+L_6+L_7+L_8) + L_9(L_3+L_7). \]

For the example under consideration, if \(i=1,\ j=3\), then

\[ \begin{aligned} 1.\quad T_{13} &= \frac{(13+123+1423)(1-565)+1653+16423+165423}{\Delta} =\\[4pt] &= \frac{\bigl[r_{13}+r_{23}(r_{12}+r_{14}r_{42})\bigr](1-r_{56}r_{65})+}{\Delta} \\[4pt] &\quad \frac{+\,r_{16}\bigl[r_{65}r_{53}+r_{42}r_{23}(r_{64}+r_{65}r_{54})\bigr]}{\Delta}. \end{aligned} \]

\[ 2.\quad S_r=\frac{\partial T_{13}}{\partial r_{65}}=T_{16}T_{53}; \qquad T_{16}=\frac{16[1-232-2342]}{\Delta}; \]

\[ T_{53} = \frac{53(1-121-161-1421-16421)+5423(1-161)+5613+}{\Delta} \]

\[ +\frac{54213+56123+561423+564213}{\Delta}. \]

For solving only problem (2) with fixed \(i\) and \(j\), the above algorithm is also redundant (to determine \(\Delta\) it is necessary to perform all operations). In this case it is more expedient to use the following algorithm, based on Hona-Aufenсamp’s state-reduction procedure [6], which differs in that the elements of the main diagonal—of the original matrix and of the matrices obtained in the course of \((n-1)\) transformations—are regularly written out and are not used in each subsequent operation. At the \((n-2)\)-th stage of state reduction we obtain the transfer \((P_k)_{ij}\), while the elements of the main diagonals give all contours (without duplications). The subsequent operation reduces to determining the contact factor. Let us consider this algorithm on an example.

Example 2. Find \(T_{13}\) of the signal graph (Fig. 1).

1. Construct the adjacency matrix

\[ [R]= \begin{bmatrix} 0&13&12&14&0&16\\ 0&0&32&34&0&0\\ 21&23&0&0&0&0\\ 0&0&42&0&0&0\\ 0&53&0&54&0&56\\ 61&0&0&64&65&0 \end{bmatrix}. \]

1. Delete the sixth node

\[ [R]^{(6)}= \begin{bmatrix} 161&13&12&14;&164&165\\ 0&0&32&34&0\\ 21&23&0&0&0\\ 0&0&42&0&0\\ 561&53&0&54;&564&565 \end{bmatrix}. \]

\[ L_2=161;\qquad L_4=565. \]

1. Delete the fifth node

\[ [R]^{(5)}= \begin{bmatrix} 0&13;&1653&12&14;&164;&1654\\ 0&0&32&34\\ 21&23&0&0\\ 0&0&42&0 \end{bmatrix}. \]

1. Delete the fourth node

\[ [R]^{(4)}= \begin{bmatrix} 0&13;&1653&12;&142;&1642;&16542\\ 0&0&32;&342\\ 21&23&0 \end{bmatrix}. \]

1. Delete the second node

\[ [R]^{(2)}= \begin{bmatrix} 121,\ 1421,\ 16421,\ 165421&13,\ 1653,\ 123,\ 1423,\ 16423,\ 165423\\ 321,\ 3421&323,\ 3423 \end{bmatrix}. \]

\[ L_1=121;\qquad L_6=1421;\qquad L_9=16421;\qquad L_{11}=165421;\qquad L_3=323;\qquad L_7=3423. \]

1. Delete the third node in order to obtain all missing circuits.

\[ L_5=1321;\qquad L_{10}=165321;\qquad L_8=13421;\qquad L_{12}=1653421; \]

\[ T_{13}= \frac{(13+123+1423)(1-565)+1653+16423+165423}{\Delta}. \]

It should be noted that finding \(S_T\) by formula (1) is convenient for finding the zero sensitivity of the transmission coefficient to variations of the parameters of any arcs.

Example 3. A measuring amplifier (Beggeli circuit) is given, whose graph is shown in Fig. 3. Find the condition of zero sensitivity to instability of the transmission of arcs \(12=-K_0\) and \(34=-K_1\):

\[ 1.\quad S_T=\frac{\partial T_{14}}{\partial r_{12}} =T_{11}\cdot T_{24} =\frac{1}{\Delta^2}(1-x_2K_1)=0, \]

\[ 2.\quad S_T=\frac{\partial T_{14}}{\partial r_{34}} =T_{13}\cdot T_{44} =\frac{1}{\Delta^2}(x_1-K_0x_2)=0. \tag{6} \]

As a result we have

\[ \alpha_2=\frac{1}{1+K_0}; \qquad \alpha_1=\frac{K_0}{1+K_0}; \qquad K_1=1+K_0. \]

In a number of cases, when analyzing complex measuring systems, one has to deal with the need to determine the multiplicative disturbance under variations of one or two parameters of the links. In this case it is convenient to express the system error through the topological elements of the graph.

Fig. 2

Fig. 3

Let \(T_{ij}=f(x \ldots y \ldots)\), where

\[ \begin{aligned} x&=r_{ab}\\ y&=r_{cd} \end{aligned} \Biggr\}\, var. \]

Then

\[ \Delta T_{ij}\simeq \frac{\partial T_{ij}}{\partial x}\,dx+ \frac{\partial T_{ij}}{\partial y}\,dy+ \frac{1}{2}\left( \frac{\partial^2T_{ij}}{\partial x^2}\,dx^2+ 2\frac{\partial^2T_{ij}}{\partial x\partial y}\,dxdy+ \frac{\partial^2T_{ij}}{\partial y^2}\,d^2y \right), \]

\[ \delta=\frac{\Delta T_{ij}}{T_{ij}}\simeq \frac{1}{T_{ij}}\left[ S_T^{(x)}\cdot x\cdot \delta_x+ S_T^{(y)}\cdot y\delta_y+ \frac{1}{2}\left( S_T^{(x^2)}x^2\delta_x^2+ 2S_T^{(x,y)}x\cdot y\cdot \delta_x\delta_y+ S_T^{(y^2)}y^2\delta_y^2 \right) \right], \]

where

\[ \frac{dx}{x}=\delta_x; \qquad \frac{dy}{y}=\delta_y; \]

\[ \frac{\partial T_{ij}}{\partial x}=S_T^{(x)}=S_T^{(ab)}=T_{ia}\cdot T_{bj}; \tag{7} \]

\[ \frac{\partial T_{ij}}{\partial y}=S_T^{(y)}=S_T^{(cd)}=T_{ic}\cdot T_{dj}; \]

\[ \frac{\partial^2T_{ij}}{\partial x^2}=S_T^{(x^2)}=2T_{ia}\cdot T_{ba}\cdot T_{bj}=2S_T^{(x)}\cdot T_{ba}; \]

\[ \frac{\partial^2T_{ij}}{\partial y^2}=S_T^{(y^2)}=2T_{ic}\cdot T_{dc}\cdot T_{dj}=2S_T^{(y)}T_{dc}; \]

\[ \frac{\partial^2T_{ij}}{\partial x\partial y} = S_T^{(x,y)} = T_{ic}\cdot T_{da}\cdot T_{bj} + T_{ia}+T_{bc}\cdot T_{dj}. \]

Thus, the second partial derivative in (7) is expressed through a sum of products of transmissions, the first term of which consists of the product of the transmission from the input node of the graph \(i\) to the beginning of the first varied arc, by the transmission from the end of this arc to the beginning of the second varied arc, and by the transmission from the end of the second arc to the system output \(j\). When finding the factors of the second term, the varied branches are interchanged.

Example 4. For the circuit of Example 3 (Fig. 3), determine the coefficient of \(\delta_x \cdot \delta_y\) \((i=a=1,\ b=2,\ c=3,\ d=j=4)\)

\[ \delta_{(x,y)}= \frac{r_{ab}\cdot r_{cd}\left(T_{ic}\cdot T_{da}\cdot T_{bj}+T_{ia}\cdot T_{bc}\cdot T_{dj}\right)} {T_{ij}} \cdot \delta_x\delta_y =K_1\alpha_2\delta_x\cdot\delta_y . \]

Taking conditions (6) into account, the coefficient of \(\delta_x\delta_y\) is equal to 1.

REFERENCES

1. V. P. Sigorskii, A. I. Petrenko. Fundamentals of the Theory of Electronic Circuits. “Tekhnika,” 1967.

2. Ya. K. Trokhimenko. Method of generalizing numbers and analysis of linear circuits. “Sov. Radio,” 1972.

3. Yu. M. Kalnibolotskii. Matrix-topological analysis of radio-electronic circuits. Republican collection Radiotekhnika, 1969, No. 11.

4. A. A. Zykov. Theory of Finite Graphs. “Nauka,” 1969.

5. P. Chua. Sensitivity of the transfer of an oriented graph to changes in the transfer of any branch of the graph. Izvestiya Vuzov SSSR, “Radioelektronika,” 1971, No. 3.

6. S. Seshu, M. B. Reed. Linear Graphs and Electrical Networks. “Vysshaya shkola,” 1971.