ON A PROOF OF THE FORMULA FOR THE TOPOLOGICAL TRANSMISSION OF A GRAPH

L. A. Naumov, E. I. Tsimbalist

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

In recent years there has been particular interest in graph theory, since it makes it possible to formulate the solution of one problem or another, and to illustrate it in a clear and concise form as a “graph” representing the phenomenon or process under study. There is also the possibility of relatively quickly solving a multitude of cumbersome and diverse problems whose complexity makes their solution by earlier methods difficult. These advantages ensure the wide application of graph theory in automation, in the theory of automatic control, electrical modeling, coding, etc.

In most cases linear graphs are used, in which every edge is oriented. Such graphs are called oriented or directed. With the aid of a directed graph one can represent an arbitrary system of algebraic (differential) equations. Since the variables in the equations of a circuit are signals (currents or voltages), the corresponding directed graph is often called the signal graph of the circuit [1].

One of the problems in the analysis of systems is the mathematical study of its model in order to determine the response of the system to an external action. The direct method of obtaining circuit functions is based on the well-known Mason formula [1]

\[ T_{ij}=\frac{x_j}{y_i}=\frac{\sum_{k=1}^{n}\Delta_k P_k}{\Delta}, \tag{1} \]

where \(P_k\) is the transmission of the \(k\)-th through path from vertex \(i\) to \(j\);
\(\Delta\) is the determinant of the signal graph

\[ \Delta=1-\sum_r L_r^{(1)}+\sum_r L_r^{(2)}-\sum_r L_r^{(3)}+\ldots; \tag{1a} \]

\(L_r^{(c)}\) is the product of the \(r\)-th combination of \(c\) non-touching contours of the graph;
\(\Delta_k\) is the algebraic cofactor of the determinant of the signal graph, equal to the determinant of the part of the graph that does not touch the \(k\)-th through path.

However, for comparatively complex circuits (especially circuits with transistors), the application of (1) is associated with the necessity of topological

analysis of the graph (identification of circuits and through paths, establishment of touching paths and circuits), often requiring very cumbersome and tedious operations, which reduces the efficiency of the directed-graph method.

The problem arises of finding an algorithm formalizing (1), the solution of which may provide a way to prove Mason’s formula. Mason himself used heuristic arguments in deriving (1) [2]. One route to a formal proof of (1) is proposed in [3]. However, its course does not give a clear algorithm free from the need for a topological analysis of the graph.

Below a derivation is proposed of the transmission formula \(T_{ij}\) for Mason’s graph, which makes it possible to solve the problem posed. Suppose we have some \(n\)-vertex graph (without loops), isomorphic to a certain physical structure (Fig. 1), where

\(y_i\) are the disturbing actions that enter the corresponding nodes of the graph through unit transmission;

\(x_j\) are the responses of the system, likewise taken through unit transmission.

The algebraic equations associated with the given linear graph \(\vec L\), written in “cause–effect” form, will have the following form:

\[ \left\{ \begin{aligned} & a_{11}x_1-a_{21}x_2-a_{31}x_3-\ldots-a_{n1}x_n=y_1 \\ & -a_{12}x_1+a_{22}x_2-a_{32}x_3-\ldots-a_{n2}x_n=y_2 \\ & \cdot\quad \cdot\quad \cdot\quad \cdot\quad \cdot\quad \cdot\quad \cdot\quad \cdot\quad \cdot \\ & -a_{1n}x_1-a_{2n}x_2-a_{3n}x_3-\ldots+a_{nn}x_n=y_n, \end{aligned} \right. \tag{2} \]

where \(a_{ij}=1\) for \(i=j\), or in matrix form

\[ \left\{ \begin{aligned} AX&=Y\\ A&=[a_{ij}]. \end{aligned} \right. \tag{2a} \]

\(A\) is nothing other than the transposed adjacency matrix of the graph \(\vec L\), with the sole difference that the elements \(a_{ij}\) for \(i\ne j\) have a minus sign. Solving (2) by Cramer’s rule with respect to \(x_j\), which is possible since \(A\) is a nonsingular square matrix, we obtain

\[ x_j=\frac{A_{1j}}{\Delta}y_1+\frac{A_{2j}}{\Delta}y_2+\ldots+\frac{A_{nj}}{\Delta}y_n =\frac{1}{\Delta}\left(A_{1j}y_1+A_{2j}y_2+\ldots+A_{nj}y_n\right). \tag{3} \]

The expression in parentheses on the right is the expansion along the \(j\)-th column of the determinant \(\Delta_j\) of the system, obtained by replacing the \(j\)-th column of the determinant \(\Delta\) by the column \(Y\). Suppose that a single disturbing action \(y_i\) acts on the system. (This assumption entails no loss of generality, since the superposition principle is applicable to a linear system.) Then

\[ x_j=\frac{A_{ij}}{\Delta}y_i \quad\text{or}\quad \frac{x_j}{y_i}=T_{ij}=\frac{A_{ij}}{\Delta}. \tag{3a} \]

On the basis of the general formula for expansion of a determinant [4], let us find

\[ \det[A]=\det[A']=\Delta. \]

\[ \det[A]=\det \begin{bmatrix} a_{11} & -a_{12} & -a_{13} & \ldots & -a_{1n}\\ -a_{21} & +a_{22} & -a_{23} & \ldots & -a_{2n}\\ \cdot & \cdot & \cdot & \cdot & \cdot\\ -a_{n1} & -a_{n2} & -a_{n3} & \ldots & +a_{nn} \end{bmatrix} = (-1)^q(-1)^k\sum_r a_{1\sigma_1}a_{2\sigma_2}a_{3\sigma_3}\ldots a_{n\sigma_n}, \tag{4} \]

where \((-1)^\kappa\) takes into account the signs of the elements of the matrix \([A']\),

\[ \kappa \text{ is the number of elements } a_{i a_i} \text{ for } i \ne a_i, \]

\[ q=n-s \]

is the decrement of the substitution,

\[ \begin{aligned} n&\text{ is the degree of the substitution (the number of vertices),}\\ s&\text{ is the number of independent cycles in the decomposition of the substitution,}\\ a_i&\text{ are the elements of the second row of the substitution.} \end{aligned} \]

The elements \(r\,det[A]\) are products of various combinations of nonintersecting contours, since the decomposition of a substitution into cycles includes different indices and, consequently, the contours do not contain identical vertices. For example,

\[ B=\begin{pmatrix} 123456\\ 134265 \end{pmatrix}. \]

This substitution corresponds to the \(r\)-th term of the expansion of a determinant of order 6,

\[ (a_{11})(a_{23}a_{34}a_{42})(a_{56}a_{65}). \]

Rewrite expression (4) in the form

\[ det[A]=\frac{(-1)^\kappa}{(-1)^q}\sum_r a_{1a_1}a_{2a_2}\ldots a_{n a_n} =(-1)^{\kappa-q}\sum_r a_{1a_1}a_{2a_2}\ldots a_{n a_n}, \]

(note that

\[ \frac{(-1)^\kappa}{(-1)^q} = \frac{(-1)^q}{(-1)^\kappa} = (-1)^{(\kappa-q)} = (-1)^{(q-\kappa)}). \]

If \(\kappa \ne 0\), \(q \ne 0\) (\(n \ne s\)), then

\[ det[A]=1+(-1)^{\kappa-q}\sum_r a_{1a_1}a_{2a_2}a_{3a_3}\ldots a_{n a_n}. \tag{5} \]

Indeed, for \(\kappa=0\) and \(q=0\) we obtain the term of the determinant expansion corresponding to the product of the elements

\[ a_{ij}=1 \qquad (i=j=n). \]

\(\kappa-q\) in expression (5) is the number of nonintersecting cycles of length greater than one. In fact,

\[ \kappa-q=\kappa-n+s=s-(n-\kappa), \]

and

\[ n-\kappa \]

is the number of cycles of length equal to one.

\[ s-(n-\kappa) \]

is the number of cycles of length greater than one.

As a result we obtain

\[ det[A]=\Delta=1+(-1)^{\kappa-q}\sum_r L_r^{(\kappa-q)}, \tag{6} \]

where \(L_r^{(\kappa-q)}\) is the product of the \(r\)-th combination of \(\kappa-q\) nonintersecting contours, which corresponds to (1a) (\(c=\kappa-q\)). From (5) it is clear that, in order to find \(det[A]\), it is necessary to know the totality of second indices \(a_1,a_2,\ldots,a_n\), which constitute some permutation of the natural sequence of numbers \(1,2,3,\ldots,n\). Since we shall now be dealing with indices, it is quite natural and convenient for this purpose to use the mathematical apparatus and notation of set theory. Write the adjacency matrix of the graph \(\vec L\) in the following form:

\[ A_b=|a_{ij}|,\quad \text{where } \begin{cases} a_{ij}=ij & \text{if there is transmission from } i \text{ to } j,\\ a_{ij}=0 & \text{if there is no transmission from } i \text{ to } j. \end{cases} \tag{7} \]

If \(C=\{1,2,3\ldots n\}\) is the set of vertex indices, and \(B_i \subseteq C\) is the set of \(j\)-indices in the \(i\)-th row (for a complete graph \(B_i=C\)), then the operation of finding the set \(B\) of combinations of \(n\) distinct elements, taken one from each subset of the collection \(B_i\), co-

corresponds to the Cartesian vector product of the subsets of the set \(B_i\) and may be represented by the formula [5]:

\[ B=[B_i]\bmod_2 . \tag{8} \]

The adjacency matrix of the graph \(\vec L\), taking (7) into account, has the form:

\[ A_b= \begin{bmatrix} 11&12&13&\ldots&1n\\ 21&22&23&\ldots&2n\\ -&-&-&-&-\\ n1&n2&n3&\ldots&nn \end{bmatrix}. \]

Taking the \(i\)-th elements outside the brackets, we obtain the table

\[ a(m_i/B_i)= \begin{array}{c|ccccc} \overline{1} & 1&2&3&\ldots&n\\ 2 & 1&2&3&\ldots&n\\ 3 & 1&2&3&\ldots&n\\ - & -&-&-&-&-\\ m & 1&2&3&\ldots&n\\ - & -&-&-&-&-\\ n & 1&2&3&\ldots&n \end{array}, \tag{9} \]

the \(m\) elements of which represent the first row of the substitution. If we carry out (8) with the elements \(B_{ij}\) from (9), we obtain the structural number \(B\), whose \(r-1\) columns are the elements of the second row of the substitution. For a complete graph, \(r=n!\)

To determine the numerator, let us return to expression (3a). \(A_{ij}\) is the algebraic cofactor obtained after deleting the \(i\)-th row and the \(j\)-th column from the determinant. Then

\[ A_{ij}=(-1)^{i+j}(-1)^p \sum_{\substack{r\\ \kappa\ne j\\ \alpha_\kappa\ne i}} \prod_{\kappa=1}^{n-1} a_{\kappa\alpha_\kappa}, \tag{10} \]

where \(p=l+h\),

\(l\) is the number of elements \(a_{\kappa\alpha_\kappa}\) (for \(\kappa\ne \alpha_\kappa\));

\(h\) is the number of transpositions of the second row of the substitution formed with the elements of the set.

\[ \alpha_\kappa=\{(1,2,3,\ldots,i,\ldots,j,\ldots,n)-i\}, \tag{11} \]

\[ \kappa=\{(1,2,3,\ldots,i,\ldots,j,\ldots,n)-j\}. \tag{12} \]

To determine the elements \(\alpha_\kappa\), we shall also use expression (8). In the adjacency matrix, delete the \(i\)-th column and the \(j\)-th row

\[ A_{B'}= \begin{bmatrix} 11&12&\ldots&1i&\ldots&1n\\ 21&22&\ldots&2i&\ldots&2n\\ -&-&-&-&-&-\\ j1&j2&\ldots&ji&\ldots&jn\\ -&-&-&-&-&-\\ n1&n2&\ldots&ni&\ldots&nn \end{bmatrix}. \]

In the table

\[ a'(k;B_i')= \begin{array}{c|ccccc} 1 & 1&2&\ldots&i&\ldots&n\\ 2 & 1&2&\ldots&i&\ldots&n\\ \hline j & 1&2&\ldots&i&\ldots&n\\ \hline n & 1&2&\ldots&i&\ldots&n \end{array} \tag{13} \]

we likewise cross out the corresponding row and column; then the \(k\) elements taken outside the parentheses, and the \(r'\) columns of the table \(B'=[B_i']_2\), will give all indices \(\alpha_k\). Crossing out a column and a row from the adjacency matrix is analogous to breaking (removing) from the graph all branches entering the \(i\)-th node and leaving the \(j\)-th node. Thus, a certain collection of elements in \(r'\) from \(A_{ij}\) will represent the through transmission of the graph from \(i\) to \(j\), while the remaining ones form disjoint contours, since the indices of the remaining elements (if they exist) \(\{k—i\beta\gamma\ldots\varphi\}\) and \(\{B_i—j\beta\gamma\ldots\varphi\}\) form identical sets, a substitution from which can always be decomposed into cycles. Moreover, these contours do not touch the corresponding path, because the elements of the substitution do not contain the indices \(i\) and \(j\beta\gamma\ldots\varphi\), which correspond to the nodes through which the through path passes. As a result we obtain that the collection of elements \(A_{ij}\) corresponds to the numerator of expression (1).

On the basis of the above, the following algorithm may be proposed for finding the transmission of a graph.

1. Write down the adjacency matrix of the graph (7) and the tables (9), (13).
2. Compute \(B\) and \(B'\).
3. Write down the transmission \(T_{ij}\) according to formulas (5) and (10).

Example 1. Determine the transmission \(T_{23}\) of the graph in Fig. 2.

1. We write down the adjacency matrix (7)

Fig. 1

Fig. 2

\[ [A]= \begin{bmatrix} 11&12&13&14\\ 0&22&23&0\\ 31&32&33&34\\ 41&42&0&44 \end{bmatrix} \]

1. We find \(B\) and \(B'\):

\[ a(m;B_i)= \begin{array}{c|cccc} 1&1&2&3&4\\ 2& &2&3& \\ 3&1&2&3&4\\ 4&1&2&4& \end{array} \]

\[ B= \left[ \begin{array}{cccc} 1&2&3&4\\ &23&&\\ 1&2&3&4\\ &124&& \end{array} \right]_{4} = \left[ \begin{array}{cccccccccc} 1&1&1&2&2&3&3&4&4&4\\ 2&3&3&3&3&2&2&2&3&3\\ 3&2&4&1&4&1&4&3&1&2\\ 4&4&2&4&1&4&1&1&2&1 \end{array} \right], \]

\[ a'(x;B_i')= \begin{array}{c} 1\\ 2\\ 4 \end{array} \left[ \begin{array}{ccc} 1&3&4\\ &3&\\ 1&&4 \end{array} \right] \qquad B'= \left[ \begin{array}{ccc} 1&3&4\\ &3&\\ 1&&4 \end{array} \right]_{2} = \left[ \begin{array}{cc} 1&4\\ 3&3\\ 4&1 \end{array} \right] \]

\[ T_{23}=\frac{a_{23}-a_{23}a_{14}a_{41}}{\Delta}; \]

\[ \Delta=1-a_{23}a_{32}-a_{23}a_{34}a_{42}-a_{12}a_{23}a_{31}-a_{12}a_{23}a_{34}a_{41}-a_{13}a_{34}a_{41}-a_{14}a_{41}- \]
\[ {}-a_{14}a_{42}a_{23}a_{31}+a_{14}a_{41}a_{23}a_{32}. \]

The main difficulty in using the proposed algorithm is determining the sign when writing the numerator and denominator of the transmission function. This drawback can be eliminated if, for example, in determining the elements of the denominator one uses the procedure of decomposing the permutations formed by the elements of the set \(m\) and the corresponding elements of the table \(B\) into independent cycles (of length greater than one); in this case, when the number of such cycles is even, a plus sign is assigned, and when it is odd, a minus sign.

To determine the numerator for given \(i\) and \(j\), we proceed as follows. We cross out from the adjacency matrix all elements of the \(i\)-th column and the \(j\)-th row, and at their intersection we place an element with unit transmission \((a_{ij}=1)\).

Analogously to the denominator, we find the elements of the numerator, taking into account that the cofactor with indices \(j,i\) is equal to unity; the plus sign is taken for an odd number of independent cycles in the decomposition, and the minus sign for an even number. This algorithm has been implemented in the program “Graph-01.”

REFERENCES

1. Mason, G. Zimmerman. Electronic Circuits, Signals, and Systems. Izd. inostr. lit., 1963.
2. S. Seshu, M. B. Reed. Linear Graphs and Electrical Networks. “Vysshaya shkola,” 1971.
3. V. P. Sigorskii, A. I. Petrenko. Fundamentals of Electronic Circuits. “Vysshaya shkola,” 1971.
4. A. G. Kurosh. A Course of Higher Algebra. “Nauka,” 1971.
5. Ya. K. Trokhimenko. The Method of Generalized Numbers and the Analysis of Linear Networks. “Sov. radio,” 1972.