'3‘?“ x: 93‘." '2‘! GI 34‘! - 4 : I w- £2.43 sad «‘5»... o .4i'251. cum 1 1 .-. 3’51“: E3? ' .Q-‘I 'r. -éafl O 5..., ‘15.; ;‘—0.‘- o '. I - v‘fia1.%l I" I ~.: é. yé-\.\. \‘3'. -.‘..: ‘5‘: an: r '3 “T ."3—:‘-~‘ ":13“ ; ‘\_" v -4 \- _- z; c : . . .:.o.."\.t.~.- ; a (2? I" ._'.~ 5‘ f'" . 4);. 3.4.. THEgé This is to certify that the thesis entitled "Some rroperties or but—bet and the Cut-bet Matrices" presented by Vichit Sirixul has been accepted towards fulfillment of the requirements for “T" 3 degree inm— '/\. I if") -//’ ,’ ./\ I , r T/ .J "1‘ 1/ \' ”i“ . T i// Ma]or professor Date June 1, 1996 0-169 SOME PROPERTIES OF THE CUT-SET AND THE CUT-SET MATRIX BY Vichit Sirikul AN ABSTRACT Submitted to the School of Graduate Studies of Michigan State University of Agriculture and Applied Science in partial fulfillment of the requirements for the degree of , MASTER OF SCIENCE Department of Electrical Engineering 1956 . Approved lé/l;# Ll 1:31 Jk~1‘“€* I Vichit Sirikul ABSTRACT This thesis is a study of a subgraph of a connected graph known as a cut-set. The cut-set is defined here on the basis of a segregation of the vertices of a graph into two, mutually exclusive, non-empty sets. The elements of the graph, each with a vertex in each vertex set, is called the cut-set. The vertex-segregation definition turns out to be more useful than the formerly employed one of defin- ing a cut-set as the set of elements which, on removal, separate a graph into two parts. A cut-set matrix is formulated-~one row for each element in a cut-set. A fundamental cut-set matrix, Agar, is defined based on the elements of a tree. The properties of this matrix, A5$—, are deduced in terms of rank, cri- teria for forming, relation to incidence and to circuit matrices, and coverage of a graph. Some interrelations of v-functions and i-functions are formulated in terms of the fundamental cut-set matrix,/3. SOME PROPERTIES OF THE CUT-SET AND THE CUT-SET MATRIX BY Vichit Sirikul A THESIS Submitted to the School of Graduate Studies of Michigan State University of Agriculture and Applied Science in partial fulfillment of the requirements for the degree ef MASTER OF SCIENCE Department of Electrical Engineering 1956 11 Dedicated to Field Marshal P. Pibuleonggran iii ACKNOWLEDGEMENTS The author is highly indebted to Dr. Myril B. Reed for euggeating the topic of this theeie, for his guidance and encouragement throughout the entire length of this work. iv GENERAL AIMS The purpose of this thesis is to present: (1) Some characteristics of the cut-set sub-graph of linear graphs; (2) the properties of the cut-set matrix; and (3) the relations between the cut-set matrix and the vertex and circuit matrices of the graph. This work has been carried on from the paper On Topology and Network Theory by Myril B. Reed and Sundaram Seshu, Proceedings of the University of Illinois Symposium on Circuit Analysis, May 1955. This thesis is based on the assumptions from that work, and in some parts of this thesis, it is necessary to abstract from the Reed-Seshu paper some properties of graphs, vertex and circuit matrices in order to clarify the relation be- tween them and the cut-set matrix. TABLE OF CONTENTS List of Figures . . . . . . . . . . . . . INTRODUCTION . . . . . . . . . . . . . . . I. THE CUT-SET . . . . . . . . . . . . . 1. Definition of the cut-set . . . 2. The properties of a cut-set . . 3. Cut-set orientation . .'. . . . 4. The cut-set of the tree . . . . II. THE CUT-SET MATRIX . . . . . . . . . l. The cut-set matrix of the graph 2. The tree cut-set matrix . . . 3. Relation between 6.» and jgmatrices 4. Rank of the cut-set matrix 12.0: con- nected graph . . . . . . . . 5. Criteria for choosing v-l cut-sets to establish a cut-set matrix of rank v-l III. CUT-SET MATRIX USE IN NET-WORK THEORY 1. Relation between £7- and 15:: matrices 2. Relation between 27 and d4 matrices 3. Current-function and voltage-function relationships . . . . . . . . CONCLUSION . . . . . . . . . . . . . . . BIBLIOGRAPHY O O O O O O O O O O O O O O O Page 4 <0 ‘0 o: (n uh a: o: +4 ta h‘ +4 h' C) 15 18 28 28 29 32 38 39 Figure .1001th (I) 10 11 vi LIST OF FIGURES Cut-set orientation . . . . . . . . General cut-set orientation . . . . Shows a cut-set c1 of the tree . . Circuit formed by cut-set elements Four tree cut—sets of graph G . . Shows the cut-set pattern formed by criterion 2 . . . . . . . . . . . Vertex CUt'BBtS e e e e e e e e e Cut-sets formed by criterion 4 . . Page 12 18 21 23 25 31 36 INTRODUCTION A study of electrical networks in general is based en the assumptions that the network consists of a finite set ef network elements connected in the form of a graph. The net- work elements can be classified according to their electri- cal characteristics as resistive, inductive, capacitive and mutually inductive elements. Vacuum tube, transistor and ether electric devices are also considered network elements. Measuring devices are used to observe the electrical phone- nena in two ways of measurement. A series or current measurement is used to ebserve the current functions of the elements by placing the meter in series with the element. The parallel or voltage measurement is used te observe the veltage functions of the elements by placing the meter in parallel with the element. A finite set of interconnected network elements, tege- ther with their erientations, forms the graph of the network. The measurements not only vary with the types of elements, but also with the geemetrie pattern er the graph formed by these elements. The mathematical relations of the funetien- al representations ef series and parallel measurements fer a netserk can be put into equations as: . l. Vertex equation1 awga (t) —._.—-o 1 Reed and Seshu, On Topology and Network Theory, Proceed- ings of the University of Illinois Symposium on Circuit Analysis, May 1955, pp. 3, 21. ' where a... is the vertex matrix of the cerresponding graph, 0‘“) is the matrix of current functions of the ele- ments of the graph. 2. Circuit equation1 B... % Cf) ="- 0 where 8‘ is the circuit matrix of the graph, mg) is the matrix of the veltage functions of the elements of the graph. The vertex and circuit equations are known as Kirch- heff's current and voltage equations. The method ef ebtaining solutiens for the network problem is te form the graph equations and solve by mathematical precedures fer the unknown variables from the given informatien. The study ef certain tepelegical characteristics ef the graph such as the vertex matrix, the circuit matrix and the cut-set matrix be- cemes an important part of this method. The tepolegical characteristics, derivable from the preperties of the vertex and circuit matrices ef the graph are presented by Reed and Seshu.2 The cut-set subgraph, first presented by Foster,3 is examined in this thesis with the intention of establishing hew effective as a basis ef netwerk study the cut-set matrix may be. 1 Reed and Seshu, gp. cit., p. 22. 213:1. 3 Fester, R. M., Geometric Circuits of Electric Netwerks, BSTJ No. B-653. I. THE CUT-SET l. nginitign of the cut-set: First place the vertices of a graph into two arbi- trary, mutually exclusive, non-empty sets A and B. A cut- set of the graph is the set of elements with one vertex in vertex-set A and the other vertex in vertex-set B. Suppose a graph G has v vertices l, 2, 3,......v, and these vertices are placed in two arbitrary mutually exclu- sive sets: as vertices l, 2,......k, in set A and the re- maining vertices kol, k¢2,.....v-l, v, in set E. The set of elements e1, e2, e3,.....em, (see Fig. l) which have one vertex in set A and the other vertex in set B is a cut-set of the graph, and the elements e1, e2, e3,.....em, are the cut-set elements. The elements with both vertices in only one set such as .mel’ em,2,.....en, are not cut-set elements of this cut-set, but they may be in other cut-sets depending en hew the vertices are placed in the twe arbitrary sets, A and B. The number of ways ef forming two mutually exclusive, nen~empty sets ef a graph increases very greatly with the number ef vertices, v. Therefore, the number of cut-sets increases likewise. 2. The properties of a cut-set: Frem consideration ef the nature ef a graph, the fel- lewing preperties ef cut-sets appear evident: b. c. d. e. f. g. h. i. A cut-set of a graph separates the vertices of the graph inte two mutually exclusive sets. This pre- perty fellows from the definitien. A cut-set element is a path Jeining the twe separ- ate sets A and B ef vertices ef the graph. A cut-set centains at least one element. A cennected graph contains at least ene cut-set. Ne preper sub-set ef a cut-set is a cut-set. The elements incident te any vertex is a cut-set. Every non-circuit element is a cut-set. A circuit element is not a cut-set. A set ef elements which separates the graph inte two parts by remeval of that set of elements is a ent‘SOte 3. Cut-set erientatign. Just as it is necessary to assign an orienting mark te elements, paths, and circuits of a graph, so it is neces- sary to assign an orienting pattern to a cut-set. Either ef the arrows cf Fig. 2 serve this purpose. 4-2 Fig. 2. Cut-set erientatien Unless otherwise specified, because ef its arbitrari- ness, the cut-set erienting arrow alignment is specified, hereafter in this discussion, as pointing from the A te the B set ef vertices in the sense of Fig. 3. Fig. 3. General cut-set erientation 4. The cut-set of the tree. The following brief listing of the properties of trees serves as a basis from which to study cut-sets and the matrices associated with them. A tree is by definition a connected subgraph of a con- nected graph containing all the vertices of the graph and containing no circuit. 1 Some basic properties of trees are: 4"e 4"be 4“ e 4"de 4".e 4": e ""e Every connected graph has at least ene tree.2 An element of a tree is named a branch. An element of the complement of a tree is named a chord. Every tree has one more vertex than branches.3 A connected graph of e elements and v vertices centains v-l branches and e-vtl chords.4 There exists one and enly one path in a tree between any twe vertices ef a tree.4 Each branch specifies a cut-set.5 Cerresponds te the "complete tree" by Cauer, Theore der linearen Wechselstremschaltungen, Akademische Verlagsgesel- schaft, Leipzig, 1941. Keenig, Theore der endlichen und unendlichen graphen, Chelsea Publishing Company, New York, 1950, p. 52. Ibid., p. 51. Reed and Seshu, e2, cit., p. 6. Unpublished class notes by Myril B. Reed. To illustrate the definition, consider Fig. 4. The tree is shown by the solid elements and the chords by the dashed elements. Corresponding to branch, b the chords 1, chl, chz, ch3, ch4, ch5, with this branch form one of the tree cut-sets. Fig. 4. Shows a cut-set c1 of the tree. Because of the fundamental character for this thesis of the statement that each branch specifies a cut-set, the following brief review without proof of the ideas involved is given. In the first place: The vertices of a connected graph may be placed in two mutually exclusive, non-empty sets A and B corresponding to each branch by: (a) Placing in vertex set A all vertices which have a path-in-tree to one of the vertices of the branch, none of these paths-in-tree are to contain the branch; (b) Placing in vertex set E all other vertices of the tree. As a consequence of this last given property of a branch: each branch defines a cut-set. It is specified here that the orienting mark of a branch specifies the orientation of the cut-set, i.e., the orienting arrow for the cut-sot (Fig. 3) is aligned with the orienting arrow of the defining branch. Some properties of the cut-sets of a tree Some properties of the cut-sets of a tree which are useful for the following developments are: l. A cut-set of a tree contains one and only one tree branch, all other elements of the cut-set as a consequence are chords.1 2. A tree contains v-l branches and so specifies v-l cut-sets. 3. A branch of a tree is a cut-set of a graph which is the tree itself. 1 Unpublished class notes of Myril B. Reed, Michigan State University. II. THE CUT-SET MATRIX l. The cut-set matrix of the graph. A matrix can be formed, corresponding to each cut-set or collection of cut-sets, as follows: minitieh: The cut-set matrix rea,=[Cij] is the rectangular array containing c rows one corresponding to each cut-set of the graph and o columns corresponding to c elements of the graph. The entries of the matrix are defined by: c11== 1 If the element ‘3 is in the cut-set c1 and the orientation of the element coincides with that of the cut-set. c11== -1 If the element e: is in the cut~set c1 and the orientation of the element and of the cut-set are opposite. c14T==0 If the element '3 is not in the cut-set c1. The shape of the cut-set matrix of the graph will be n x e, where n is the number of cut-sets: Columns =-. element of graph rows = all possible cut- '80. :: sets of the graph lO 2. The tree cut-set matrix. A tree cut—set matrix,.0r, may be formed by consider- ing only the v-l rows ofudag which correspond to the tree. Theorem:;: The tree cut-set matrix,.4?r, of the graph containing v vertices has the rank of v-l. Prggf: Since there are v-l rows in any matrix,.£§}, corresponding to a v-vertex e-element connected graph,,€%-is (v-l) x e. Hence, the rank ofzeg-matrix can not exceed v-l. Order the rows and columns of the tree cut-set matrix .427- such that the first v-l columns (right to left) and the rows (t0p to bottom) correspond to the same ordering of the defining branches. The cut-set orientation is the same as the branch orientation which defines the cut—set. The first square sub-matrix of .8, of v-l rows and columns has the diagonal entries, °ll’ c22,.....c11, equal to t1 and all other entries zero. The leading (v-1)x(v-l) sub-matrix of 49? matrix can thus always be made the square unit matrix of rank v-l, i.e., brahches chords b1 b2 b3 eeeeebv_1 ‘ 01 .2 oeec .4 c1 r l O O ..... O t x x .... x l c2 0 1 O 0.... O . 0.0.x ’31“ 03 O O 1 eeeeo O : eeee oo o e o eeeee e . e e eeee o I cv..1 LO 0 O eeeee 1 X X eeee X‘d ll Therefore, the rank of tree cut-set matrix will not be less than v-l. Then, the rank of the tree cut-set matrix 499 is v-l. Corollary:;;_; Removal of any one of the tree cut- sets reduces the rank of the matrix,,43r, by one. 25222: This can be easily seen by removing any one tree cut-set, the number of rows of flrwill be reduced from v-l to v-2, and the rank of the matrix will not exceed and will not be less than v-2. Hence, the rank of the £7 matrix is reduced by one. 3. Relation between g. and gun. matrices. The circuit matrix1 associated with each graph con- tains one row corresponding to each possible circuit and one column corresponding to each element of the graph. The k1 entry of the circuit matrix is 1 if element eci is in the circuit ck with the same orientation, -1 if the element ace. is in the circuit ck with the opposite orientation, and 0 if the element ac; is not in the circuit ck. Lemma 1.2: An even number and only an even number of elements of any cut-set are contained in any circuit. See Fig. 5. These elements occur in pairs. 1 Reed and Seshu, op. cit., p. 11. Gm Fig. 5. Circuit formed by cut-set elements nggf: Consider the forming of the sequential label- ing which defines a circuit.1 Any vertex of the circuit may be taken as the starting point of the labeling. Consider a vertex in the A set. Incorporating any one cut-set element into the circuit introduces a vertex of the B set into the circuit. A second cut-set element must then be contained in the circuit in order that it be possible to complete the defining labeling, i.e., include another, or the starting vertex, of the A set in the circuit. The foregoing pattern is general. The cut-set elements contained in circuits occur in pairs. Hence, the lemma. A fundamental relation exists between the cut-set matrix, gas and the circuit matrix, ,6... , in the form indi- cated by the following theorem. Lemmg 2,2: If the columns of Aéha and [an are arranged corresponding to the same element ordering and if X is any column of 66., then a X g 0 1 Reed and Seshu, op. cit., p. 5. 13 2322:: For a connected graph G, write the circuit matrix Ba. and the cut-set matrix &with columns correspond- ing to the same order of elements of the graph. Consider an arbitrary column of 65.. , X, corresponding to the i-circuit. The J row of 85- corresponds to the element 0‘] also the rth row of emcorresponds to rth cut-set of the graph G. (1) If the element 09 is not in the cut-set cr the entry on =0, then (a) If the element “J is also not in the i-circuit, the entry x1= 0, therefore, ch ox1=0x0 = O (b) If the element «.3 is in the i-circuit, the entry x1 will be non-zero and equal to :1, so ch . x1===0x (11:1): 0 (2) If the element ‘1 is in the cut-set or, the entryr V ch of’Ca, will be non-zero and equal to :1, then (a) If the element ‘1 is not in the i—circuit, the entry x1 is zero, and ch . xix—(1:1) x O .-= 0 (b) If the element 9‘1 is in the i-circuit, the entry x1 will be non-zero and equal to :1. Of the preceding four conditions, l-a, l-b, 2-a, and 2-b, only 2-b introduces other than zero into the product. According to Lemma 1.2, the elements of a graph common to a circuit and a cut-set occur in pairs. It is sufficient 14 therefore to consider all possible cases for one pair of elements. The following tabulation.exhibits the four possible element, cut-set and circuit combinations: I II 4 W5 C” ”D C *3 .————-q=—-. -——¢mmE——- r cut-set: cl 1% EIE “EI J circuit: .1 -1 +1 +1 (11)(+1)+(1'1)(-1)= 0 (11)(+1)+ ($1)(+1)=0 ——————§;2. .——4s————. k. k. 1 _J5 k r cut-set: 1:1 1:1 El; fl J circuit: 41 -l ..1 +1 ($1)(-1)*('-'-1)(~1)-0 ($l)(-1)*(;1)(*1)=' 0 The theorem, therefore, follows. Theorem 2: If the columns of &and flare arranged corresponding to the same element order and.¢fi;and fizz are the transposes of‘éa,and.£fi, than 6.152ch 6., e150 15 Proof Since ,&X=o from Lemma 1.2 where X is any column ofBaC, at once gagzgo then [’90 3&1”: lag/gage. Corollary 1.2: There exists a linear relationship among the columns of the matrix Rawhich corresponds to the elements of the cut-set. 12221;: Since Haj/so , for 9 any column Office, the columns of 34, are linearly related. 4. Rank of the cut-set matrixljggof connected graph. The rank of the cut-set matrix/64. of the graph can be found as follows: Lemma 1.3: The rank of the cut-set matrixydagof a connected graph is at least v-l. nggf: Every connected graph has a tree and the cut- set of this tree is a sub-set of all cut-sets of the graph. Therefore, the tree cut-set matrix/{g-is a sub-matrix of the cut—set matrix &. Since .87 has the rank of v-l by Theorem 1, the rank of the cut-set materAéh.is not less than v-l. Lemma 2.3: The rank of the cut-set matrix 4£Lof a connected graph can not exceed v-l. 16 Proof: Let rb represent the rank of‘Ba, rc represent the rank of/eé, and e the number of columns of Ba and rows / I one. If, as shown by Theorem 2, 54,551) then1 4: I‘bir ,..O c or rc :3 e - rb But,2 rb- e-vcl’ hence r3 5 v - l and so the Lemma. Theorem 3: The rank of the cut-set matrix A52 of a connected graph is v-l. nggf: This theorem follows from Lemma 1.3 and Lemma 2.3 above. For the rank of& cannot exceed nor be less than v-l, hence it is v-l. Theorem 4: Every set of v-l cut-sets such that the matrixaéz of these cut-sets has a rank of v-l includes every element of the graph. m: Let the v-l rows of .6 be brought to the first (v-l) row position of ék,and rearrange the columns so as to make the leading square sub-matrix of order v-l non-singular. This is certainly possible becauseeé? has a rank of v-l. It is sufficient to show that a column oflga in which the entries of the first v-l rows are zeros will not exist 1 Hohn, Franz E., Linear Transformations and Matrices, University of Illinois, class notes. 2 Reed and Seshu, gp. cit., p. 14. 17 unless all entries of this column are zeros. This proposi- tion may be proved by contradiction. Assume that there exists a kth column of¢such that the entries of this column in the first v-l rows are zeros but all other entries of this column are not zero. The kth column will not be one of the first v-l columns since the leading v-l square matrix is non-singular. The kth column may be interchanged with the vth column. Now, there is a non-zero entry of this th row where r is greater than v-l. The rth column in the r may be interchanged with vth row. Then, the leading square sub-matrix of £4 of order v becomes non-singular. Hence, (Ea,has a rank of at least v which contradicts theorem.3 above that&has a rank v-l. A Therefore, a non-zero column of‘tflgwith zero entries in the first v-l rows will not exist unless all entries of this column are zeros. Hence, every cut-set element appears in the first v-l rows of‘fiaewhich is the proposition of the theorem. 18 5. Criteria for choosinggv-l cut-sets to establish a cut- set matrix of rank v;;. The number of cut-sets for any graph may be very large and in all but the simplest graphs the cut-set pattern is complex. The set of cut-sets, from which a, a matrix of v-l rows and of rank v-l, may be established can be specified by any one of the following criteria: Criterion_;: Form the tree cut-sets according to section I, paragraph 4. The tree cut-set matrix;é} of the graph has a rank of v-l by theorem 1 and the cut-set matrix éh'of rank v-l covers all elements of the graph by theorem 4. Example 1: A connected graph G contains 5 vertices es, and eg. Choose as a tree the v-l:=4 elements, e1, e2, c3, and e4 shown in Fig. 6. -— ----- "’ --- x‘ , 3' JL><”' e %”’ ea. “- ‘ ,I’II A \\\1 VI :: _-___ \ V 96' Y; 7 - 5 Ca Ca 63 C4 Fig. 6. Four tree cut-sets of graph G. 19 The cut-set: c1 contains branch 91 and chords e5, 09 c2 contains branch oz and chords e5, as, ea, 99 c3 contains branch eg and chords e6, e7, 93. e9 c4 contains branch e4 and chords 9?, 63 By choosing the cut-set orientation to coincide with that of the defining branch and placing the columns corres- ponding to the branches in the leading positions, the cut-set matrix 4g'rof the graph of Fig. 6 becomes branches chords t‘JT—"_“\ r** t"‘ ‘Ei e2 e3 e4 65 e5 97 e3 ‘7i3 I cl 1 O 0 O i l O O O l C c2 0 1 o o ‘.1 1 o 1 1 gr; '. c3 0 O l O : 0 l l l l 0 c4 ‘ O 0 0 1 i O O l l O l The cut-set matrix can be partitioned corresponding to the branches (er...) and the chords (€713), i.e., ’faf"l:499” 455WL:]“1:Z(4§;um;7 Since ‘Z{ is unit matrix of rank v-1-4, the rank of €7- is v-1=r4 and covers all elements of the graph by theorem d. By ordering the entries in1§§, as in this example, a (v-l) x (v-l) unit matrix can always be located in the leading position. Hence, the rank of 4r is v-l. Criterion 2: Choose a tree of the graph and order the cut-sets such that the first cut-set is a tree cut—set. 20 Each succeeding cut-set must include one new branch and some or all of the chords and may include some or all of branches and chords in the preceding cut-sets. The cut-set orientation may be made to coincide with that of the new branch. The cut-set matrix €?formed by this criterion has a rank of v-l and fits the condition specified. This can be shown by rearranging the columns of the cut-set matrix 6? so that the 1th column corresponds to the new branch in- cluded in 1th cut-set, the leading square matrix of order v-l is triangular with 41's on the main diagonal. Hence, the @matrix has a rank of v-l and will include all elements of the graph. Example 2. Consider the connected graph G of Fig. 6 with 5 vertices and 9 elements. Choose a tree with v-l==4 branches as cl, e2, es and e4, the remaining elements 65, c6, e7, ’8 and eg are the chords of the graph G. Form the cut—set c1, c2, c3 and c4 such that: 01 is a tree cut-set which contains only one branch el and chords e5, eg; the c1 orientation is made to coin- cide with that of e1; c2 is a succeeding cut-set which contains a new branch oz and includes branch el and chords e6, 63, the orien- tation of oz is made to coincide with that of oz; 21 c:S contains a new branch 93, includes branch el and chords e5, °6’ 07 and as, the es orientation is made to coincide with that of as (element eg is not in this cut-set); c4 contains a new branch e4, includes branch es, and chords e6, eg, the c4 orientation is made to coincide with that of o4. VS Fig. 7. Shows the cut-set pattern formed by criterion 2. The cut-set pattern by this criteria is shown in Fig. 7 and the cut-set matrixfi§30f the graph is: branches chords ’61 °2 433_—’;Z ’55 °6_d~;7 0s 133‘ c1 1 O O 0 g 1 O O O l .. c2 «1 1 o g o 1 o 1 0 c3 -1 0 l O l"1 l l l 0 c4 1 O O -l l O l 0 O -l The rank of this cut-set matrix,£? is v-l and this cut- set matrix,£3 covers all elements of the graph. 22 Criterion 3: Form the cut-sets according to the de- finition in section I, paragraph 1, by placing one and only one vertex in set A and the other v-l vertices of the graph in set B. There will be v cut-sets for the graph of v ver- tices formed by this criteria. Any set of v-l of these cut-sets will form.the cut-set matrix,«ék, of rank v-l. Ppppg: Define the cut-set orientation as from set A to set B. The elements of any one of these cut-sets are the element incident to that vertex. The 01th row of the cut-set matrix.£g,which corresponds to vertex v1 is the same as the 1th row which corresponds to the v1 vertex of the incidence matrix 61... Therefore, the cut-set matrix 8,, formed by this criteria is the same as the vertex matrix CL; of the same graph. Since vertex matrix 614 has a rank of v-l1 and includes all the elements of the graph, the cut- set matrix 8,, of the graph will have a rank of v-l and covers all the elements of the graph. The cut-set matrix formed by this criteria may be named as "Vertex cut-set matrix a..- of the graph. Corollary: Any incidence matrix,a4, is a sub-matrix of the cut-set matrix.é%. M: From the manner of constructing 49y, @y’ an, where a4 is the incidence matrix of the graph. 1 Reed and Seshu, _p. cit., p. 8. 23 Example 3. Consider the same connected graph G as in Example 1 and 2 as reproduced in Fig. 8. The vertex cut- sets c1, c2, c3, c‘ and c5 are formed corresponding to ver- tices v1, v2, v3, v‘ and v5 of the graph and the cut-set orientation coincides with the elements oriented away from v1, v2, v5, v4 and v5 respectively. The vertex cut-set pattern is shown in Fig. 8. Fig. 8. Vertex cut-sets. The vertex cut-set matrix 49v is: all elements of graph x _fe1 e2 e3 e4 e5 '6 e7 '8 3;; c1 '_.._._v1 1 0 O O l O 0 O l @v” c3 ,va 0 -1« 1 o -1 o 1 0 c4.— Vg O O -1 1 O -1 O 0 -1 c5 -15 L o o o -1 o o -1 -1 o Any vertex cut-set matrix of v-l rows (4 rows) will be of the rank v-l-I4 and includes all elements of the graph. 24 Criterion 4: Form the cut-set in such an order that the first cut-set is a vertex cut-set of the graph. Each succeeding cut-set is formed by taking a new vertex and may include some or all vertices used in forming the pre- ceding cut-sets. The cut-set orientation may be made to coincide with that of the element directed away from the new vertex. 2322:: Arrange the leading columns of the cut-set matrix‘éz.formed by this criteria, in correspondence with a “new" element introduced by each succeeding cut-set. The leading square matrix of order v-l is triangular with +l's on the main daigonal. Hence, the cut-set matrix @4 has a rank of v-l and includes all elements of the graph. Example 4. For the connected graph of Fig. 9, the cut-set matrrx dghrmay be formed according to criterion 4 by taking the first cut-set c as a vertex cut-set corres- l ponding to vertex v1 and oriented away fromv1 with element e1 corresponding to the 18t column. Form c2 at vertex v2 with orientation away from v2, make the column corresponding to element °8 the 2nd column. Form c3 from v3 and v2. Orient c3 away from.v3-v2 and make column 3 correspond to element e3. Form the cut-set c4 from v4 and v3 oriented away from v4-v3. Locate the column corresponding to element 4th e4 as the column. The cut-set pattern is shown in Fig. 9. 25 Fig. 9. Cut-sets formed by criterion 4. The cut-set matrix 495 is: .1 .8 03 .4 02 05 06 O? .9 _ c1 1 o o o o 1 a o 0 1’7? 6; __ c2 -1 1 o o 1 o 1 o 0 c3 -1 1 1 o o -1 1 1 0 c4 L o o o 1 -1 -1 -1 1 -1 This cut-set matrix Ag; has a rank of v—l and includes all elements of the graph. Theorem Q: Let the matrix .9 be cut-set matrix of rank v-l. Then a square sub-matrix of order v-l of 45? is non-singular if and only if the columns of this sub-matrix correspond to a set of branches. 2222;: (1) Consider the columns of a sub-matrix ofWé? which correspond to the branches of some tree T. Then there exists a set of tree cut-sets for this tree. 26 Let these cut-sets be arranged so that: ’81-: [U 81-12.] Let the columns of.£? be arranged in-the same order as those of,4£}, then ’C? “ [443ul"€?aa;] where the columns of.{2zcorrespond to the branches. Now the rows of,4?}are a basis for the set of all cut-sets of the tree (T-cut-set) and so are the rows of‘rfg> (rank v-l). Hence, there exists a non-singular transformation matrix .8 so that: $87. =6 from which ”Ly/@171] .__—_= Leaf“) so that ,Os,{_?,, is non-singular. Hence, the sub-matrix of 8 corresponding to a tree is non-singular. (2) If the sub-matrix‘,62}does not correspond to the v-l branches of some tree, at least one column other than those of,1§u.corr65ponds to a branch. There is some row of,£fl, then with v-l zero entries but not all zero entries. Place this row in the vth position with the v-l zeros in the th column. first v-l columns and any non-zero entry in the v Then,£§h.has a rank of v which contradicts the known pro- perty of rank v-l of,1EL,. Hence, if 4?; is non-singular, it corresponds to a tree. 27 Corollary 1.6: If x9,- is the matrix of the tree cut- sets for any tree of a connected graph G arranged so that £1 = [a 16772.] and if ,8 is the matrix of rank v-l of any set of v-l tree cut-sets of graph G with columns arranged in the same order as ’81 , then 3 -/@” ’61- —-I and ’87, ”/8" )8 where 69.8,,8mJ and ,6)” is square. 28 III. CUT-SET MATRIX USE IN NET-WORK THEORY 1. Rglation between ,9; angimatrices. Theorem 6: Lot 121 represent the tree cut-set matrix and EL, the c-circuit matrix for any one tree of connected graph G. Let ,er and K; be arranged so that they are par- titioned corresponding to chords and branches of the tree as a4gr"‘l;427u Z¥r_] chords tun gr. 5’ [We 8¢111 Chords {1“ where 2‘7 and Z!a are v-l and e-v+l order unit matrices and respectively. Then, we have 167/! B "' 8519.. 6:19.: “”8471. £1 =[" 312.2%] &. =[uc "" fl] Proof: The relations £TBE=0 ...............(1) Be£¥=o ...............(2) are valid by Theorem 2 since Aer and fig are sub-matrices or £4 and B“. e Therefore and! as. 61' ’35 = L37" 2‘7] A 65...] f 0 from which em 2‘3 4- 2(1- 3812... ,_..._ o / Since Zl. = a ”1‘“ rent + 33.12. = 0 / and so £1“ = “Baas. By taking the transpose of both sides or by substituting/QT andfic. in equation (2) there results gala. = ”,8?" The substitution of this relation into ’91. and 3c. produces / gr :5 [" 5cm. 2‘7] a =- [ 2e w...) 2. Relation between fLand geometric“. and Theorem 7: The vertex matrix, a“, of a connected graph G can always be arranged and partitioned so that a» an. ad’ = 44, an where 41.118 of order (v-l) x (v-l) and is non-singular. There exists a set of tree cut-sets in G for which the matrix of tree cut-sets is given by g,- ”[rérll 26’] g [d,: all Z‘r] where Qmis the unit (or identity) matrix of order v-l. 30 Proof: Sincea‘ has a rank _v-l the columns and rows of 44. can be permuted so that the non-singular sub-matrix of order v-l appears at the upper right hand corner so that all 4/3, X‘ = éa/ 4am] and dzzof order v-l is non-singular. There exists a set of c-circuits for which the c-circuit matrix,:l EC , is 1 b I / g ven ‘ y 5a == [24¢ gC/l] == [24¢ —d/I 4:; where 6‘": __ a; 471/ Since, Theorem 5 gives «€711 ‘7 " gm. .1 th.n £7” = a [2 d// and .1 £7 =[’€ru ZZTJ‘g [4/1. dxxa‘r] Corollary 1.7: 4/ = a“; x67- and A? == 47; 6?, Proof: Since 2118 of order v-l and non-singular, from Th orem ‘7: _. . a4]: " ’87- :: 4/; £411 4/; 76,-] =— [4,, 4,; J ._, 4, Therefore, an. ,é, :: 4', and g, = 6232. a, 1 Reed and Seshu, pp. cit., p. 18. 31 From the result given by this last corollary: Cr and the incidence matrix of the tree, 2"” a, a and the incidence matrix of the tree, “Ia—‘V’Cr Example . Consider the graph of Fig. 10. Fig. 10. The incidence matrix is: a b c d e f F 1 o 1 1 01 4a -1 1 o o o :5 __ o - 1 o -1 J '1 1 o 1 1 422, = O l] , and dz: _L -1 !_ -1 o 1 -1 0 Then: 11 T r 1 o 0'1 15311=¢2J1€Z‘=' 0 '1 ’1 O 1 _g -1 (L L0 -1 1 o -1 J IT -1 1 1 o ...-.-. o 1 -1 o 1 o l -1 o o o 1 32 The vertex matrix CL.can also be determined from the tree cut-set matrix,,£2r, and the tree incidence matrix in accordance with a -' an. A9,. 3. Current-functpon and voltage-function relationships. Two of the fundamental postulates of electrical net- work theory take the mathematical form of vertex and circuit equation.1 The vertex equations are 4Z(é)=o ..............(A) where the matrix awrepresents the functions i(t) associated with the network elements, and the circuit equations are fifecfl=o .............(B) where the matrix3g(¢)represents the functions v(t) associated with the network elements. A variety of interrelations among the current func- tions, i(t), and among the voltage functions, v(t), can be expressed in terms of A97 and its sub-matrices. Theorem 0: If ,é;,is the tree cut-set matrix of the graph G and &C£)is the matrix of current functions, i(t), associated each element of the graph, than E7— 099 (‘6) =5 0 Reed and Seshu, _p, cit., pp. 21, 22. 33 Proof: Let [1 be a tree cut-set matrix of graph G, and .5.“’the matrix of current functions, i(t), associated with each element of the graph. Since flrgfljéa by corollary 1.7, then [674“): Zédje“) =r '—J ‘24I&.[;2c2é‘¥);7 But by the fundamental postulate defibw=o Therefore: ’6’. ‘2“): a 24. n 0 ._._. 0 Theorem 9: If ,8, is a tree cut-set matrix, We“) and M“) are the matrices of voltage functions associated with all elements of a graph and the branches of the tree, than (c __ ’ grye ) " [69/23 &13 ‘f' 2(1'] ‘ Hid) £32212: Let E, be a tree cut-set matrix of graph G, 7E“) the matrix of voltage functions associated with ele- ments of G and let 3‘- be the circuit matrix of the same tree of the graph. Partitioning g,- and 6c corresponding to chords and branches, ya“) can be partitioned corres- ponding to chords and branches as 7/2, (c) 2‘35!) == 2%; (£1 34 (t) Then ,Qr U. (0 - [IQ-r” 26171»; (9] g 49,-” Z‘é)+ m (t) Since, by Theorem 8, ,6,” = _.. 33,1, by direct substitution 2,. m we- 4.1.x w . 2r. «2 From fundamental postulate (B), 3‘ 2!; a): e [2" Ben] 772:» = 0 and so ya) BQ‘thei-g 0 mar) = -5c117%(‘) Using this value of «@7- ye (é): -- 6:12. [6411.“ ({)J 4- ”i (f) x—(c‘) Lac 12 Beta 1" ZIT]° yb (10 Theorem 10: The functions of Zélilassociated with the chords of a tree of a connected graph G, can be ex- pressed in terms of the functions ofybcei associated with the branches of the same tree. 35 Proof: Let 8‘ and E, be c-circuit and tree out- set matrices of a tree of a connected graph G. Partition 3.. and ,8, to correspond to chords and branches as 6e. " [24c gels] .427 "l:4?7u 227:] Let M“) and 73“) represent the voltage functions associa- ted with chords and branches of the tree respectively, then Zfic‘t’ fimg[waj Since, by fundamental postulate (B), 6.: We“): 0 £7“- 6.2/2.1[7/c (0] = 0 WA to) and 746» + em 2/. a) = o B Theorem 6 y 6‘3]; =s “/6?” therefore. 24; (c)__/@;.',, Z2 we. 0 746*) =22. We “’ Corollary 1.10: The voltage functions 7/: (9 associated with all elements of the graph can be expressed in terms of the voltage functions yé («0 associated with branches of any tree of the graph as %(o=/€;%(e) 36 Proof: Since 7%“) ma) - zxgée) on substituting the value of ig‘flin terms of mcafrom the theorem, there results I 6%) 7: (f)_ £7“ 2/6 2z2(£) 3?» == [: -] 7y;<£i ’21. 8/ Bill: T” / [a] 3 ”3" nd 0 / a s 79;.c" =3 «691-1505“) Example 6. Consider the graph given in Fig. 11 and suppose the voltage functions associated with the branches of a tree of G are known as Va! Vb and v6 which are associa- ted with branches a, b and c respectively. 3? The problem is to find the voltage functions associated with all elements of the graph /’ 2/8 ct): Ea(t) vb(t) vc(t) vd(t) V°(t) am] First write the tree cut-set matrix for this tree with elements arranged in the same order as in a b c d e f c“ 1 O O O. 1 1.1 453.== cb O 1 O l 1 1 cc 0 O 1 1 1 0 1. -1 The matrix %‘0 is in the form of single column as va a): vb w v. Then the 24“) matrix can be found by 2/8 t" =—.. ,8; 24 <0 which in detail is , _ 1‘ 1 v.7 r'1 o 01 va 1 Vb 0 1 0 ‘P v 1 Vb Va 0 o 1 8‘ vc zyga9 vb == “ vd = O 1 l " vb .1 vs No va 1 1 l ' Va +vb cvc L'f t 1 1 0 L Lva +Vb 38 CONCLUSION The cut-set and cut-set matrix properties studied here are useful in solving net-work problems. For instance, the node transformation equation1 ZZ;(HD==‘61’ZZ;(%Q where 7);“, are arbitrary functions, obscures the fact that the v(t) of a tree determine all the v(t), whereas in terms of the cut-set matrix 2Z;‘~”’== /€?;:13§r(£) in which ”6.“, is the matrix of voltage functions corres- ponding to a tree. Furthermore, the cut-set matrix seems to be more general for the vertex matrix is always a sub-matrix of the cut-set matrix. Also the circuit matrix can be found from matrix,{? . It is here suggested that the cut-set system be considered as the fundamental i-function postulate in place of the vertex equations of Kirchhoff, i.e., '6?“29 CiUh== C) 1 Reed and Seshu, o . cit., p. 26. 39 BIBLIOGRAPHY Cauer, W., "Theorie der linearen Wechselstromschaltungen" Akademische Verlagsgeselschaft, Leipzig, 1941. Foster, R. E., "Geometric Circuits of Electric Networks" BSTJ No. B-653. Koenig, D. "Theorie der endlichen und unendlichen graphen," Chelsea Publishing Company, New York, 1950. Le Corbeiller, P., "Matrix Analysis of Electric Networks", Harvard Monographs in Applied Science, Number 1, Harvard University Press, 1950. Reed, Myril B. and Sundaram Seshu, "On Topology and Network Theory". Proceedings of the University of Illinois Symposium on Circuit Analysis, May 1955. MICHIGAN STATE UNIVERSITY LIBRARIES i n; iiljllllIIIIIlIli 3 1 3169 4288 I 93