Cut-set 626i1d

Fundamental Circuits And Fundamental Cut-Sets Yashaswini Hegde

Abstract—The objective of this paper is to discuss the relationship between fundamental circuits and fundamental cut-sets such as • with respect to a spanning tree a chord that determines a fundamental circuit τ occurs in every fundamental cut set associated with the branches in τ and not in any other. • every circuit has even number of egdes in common with any cut-set • fundamental cut-set matrix and transpose of fundamental circuit matrix are orthogonal.

•

•

I. I NTRODUCTION Fundamental Circuits:- A spanning tree of a graph is a sub graph, which is a tree and connects all the vertices together. Suppose if an edge is added between any two vertices of a tree a circuit is created, because there already exists one path between any two vertices of a tree.Suppose if a spanning tree T is considered in connected graph G, adding any one chord(an edge which is absent in T but present in G)to T, will create exactly one circuit. Such a circuit, formed by adding a chord to a spanning tree, is called fundamental circuit. A graph will have fundamental circuits as many as its chords with respect to its spanning tree, under consideration.Along with this, – Circuit is a fundamental circuit only with respect to a given spanning tree – A given circuit may be fundamental with respect to one given tree, but not with respect to a different spanning tree of the same graph. – Tough the number of the fundamental circuits in a graph is fixed,the circuits that become fundamental, change with the spanning trees. Here is a graph and its spanning tree Fundamental Cut-set A cut-set is a set of edges whose removal would disconnect a

Department of Computer Science, University of Mysore, Mysore – 570006, Karnataka, India

Figure 1.

A Graph,G

Figure 2.

A Spanning Tree Of The Graph,T

graph. And the concept of the cut-set is closely related to circuit. If the vertices of a non directed graph G=(X,A) are partitioned into two sets X1 ad X2 where X1 belongs to X and X2 is the complement of X1 in X.Then the set of links of G whose terminal vertices lie one in X1 and other in X2 is called cut-set of G. To understand the relation between the cutset and fundamental circuit it is required to understand the relation between a spanning tree and the cut-set. Since a spanning Tree is minimal set of edges that connects all the vertices and the cut-set is minimal set of edges that disconnects some vertices from the other, both should have at least an edge in common. The fundamental cut-sets with respect to a spanning tree T is defined as the n-1 cut-sets each one of which contains one and only edge

•

which is in the spanning tree T. And thus if T is a spanning tree of a non-directed graph G, the fundamental cut-set determined by an edge ei of T is composed of ei and those edges of G not in T, which when added to T lead to fundamental circuits containing ei . Fundamental cut-set and Fundamental circuit Matrices The fundamental circuit is of the form Bf =[IkB] where I is the unit matrix. Similarly Fundamental cut-set matrix is defined as Cf =[CkI]

•

•

•

• •

Generation of a graph, which can be generated randomly. Creation of a spanning tree for the given graph. This is generated using DFS technique and in the resulting adjacency matrix only branches that in the array resulting from the algorithm is retained as 1 rest is set to 0 Generating the the fundamental circuit matrix. This is generated as a matrix of chord X branch with respect to the spanning tree. Introducing a chord a cycle is detected as the corresponding row is updated. Generating the fundamental cut-set matrix. Checking for the defined relation. Checking both matrices are orthogonal.

The transpose of fundamental circuit matrix • BfT and Cf the fundamental cut-set matrix C Generating the fundamental cut-set matrix and are orthogonal. ie BfT .Cf = 0. checking for the relation(even number of edges) This information tells that- Each circuit cut by and also checking both matrices are orthogonal are a cut- set has an even edges in common with explained below. the cut-set. BfT + Cf = 0. II. P ROBLEM S TATEMENT- R ELATION B ETWEEN F UNDAMENTAL C UT-S ET AND F UNDAMENTAL C IRCUITS Prove the relation between Fundamental Circuit and all fundamental cut-sets. Such as • The fundamental cut-sets with respect to a spanning tree T is defined as the n-1 cut-sets each one of which contains one and only edge which is in the spanning tree T. • Each circuit cut by a cut- set has an even edges in common with the cut-set. • The transpose of fundamental circuit matrix BfT and Cf the fundamental cut-set matrix C are orthogonal. ie BfT .Cf = 0.

The following figures shows all fundamental circuits and respective fundamental cut-sets.

Figure 3.

Fundamental Circuit, with edge e3

Figure 4.

Fundamental Circuit, with edge e4

A. Data Structures Used •

•

•

Double dimensional array to hold the fundamental cut-set. Double dimensional array to hold intermediate transposed matrix Double dimensional array to hold the result of the multiplication.

B. Development Of Algorithm The development of the algorithm contains 6 stages.

The fundamental circuit matrix is -

Figure 5.

Fundamental Circuit, with edge e7

Figure 8.

Fund cut-set,with edge e2,e3,e4

Figure 6.

Fundamental Circuit, with edge e9

Figure 9.

Fund cut-set,with edge e4,e5,e7,e9

c c1 Bf = c2 c3 c4

e3 1 0 0 0

e4 0 1 0 0

e7 0 0 1 0

e9 0 0 0 1

e1 1 1 0 0

e2 1 1 0 0

e5 0 1 1 1

e6 0 0 1 1

e8 0 0 0 1

let us consider cut-set, e4,e5,e7,e9 due to the removal of a edge e5 in a spanning tree. From the fundamental circuit matrix get the rows which contain e5=1. Such rows aree1,e2,e4,e5 -considering only ones in row c2 0 10011100 • e5,e6,e7 - in row c3, 0 0 1 0 0 0 1 1 0 • e5,e6,e8,e9- in row c4 0 0 0 1 0 0 1 1 1 To prove the relation-1, it can be checked that e5=1 in all the three above mentioned fundamental circuits. and to prove the relation 2- for a row in cut set with branch e5=1 all the fundamental circuits with e5=1 ie e5 on are checked by doing L ringsum operation and see any two bits are reset. If so, that means there are two branches are common. •

Figure 7.

Fund cut-set,with edge e1,e3,e4

The fundamental cut-set matrix with respect to the same spanning tree. k k1 k2 Cf = k3 k4 k5

e3 1 1 0 0 0

e4 1 1 1 0 0

e7 0 0 1 1 0

e9 0 0 1 1 1

e1 1 0 0 0 0

e2 0 1 0 0 0

e5 0 0 1 0 0

e6 0 0 0 1 0

e8 0 0 0 0 1

L

0 1 1 1 0 0 1 0L 0 010011100 011100100L001000110 011100100 000100111 It can be observed exactly two fields have been L reset after the ringsum operation. From the above described fundamental circuit it can be observed that its of the form

Figure 10.

Figure 11.

Algorithm 1 create sptree(int vertex,int numVertices) 1: setting the visiting vertex as 1 to avoid cycles 2: g visited[vertex]=1 3: for (i = 0; i <= numV ertices; i + +) do 4: if (g adj list[vertex][i] == 1) then 5: g dst lbl[i].dist = g adj list[vertex][i] 6: g dst lbl[i].nei node = vertex 7: iff neighbour exists and not yet visited 8: if (!g visited[i]) then 9: go visit next 10: create sptree(i,numVertices) 11: end if 12: end if 13: end for

Fund cut-set,with edge e6,e7,e9

Algorithm 2 create fundckt(int vertex,int ptr,int vstart) 1: g visited[vertex]=1 2: for (i = 0; i <= numV ertices; i + +) do 3: if (g adj list[vertex][i] == 1) then 4: if (!g visited[i]) then 5: path[vertex][i]=i 6: ptr++ 7: create fundckt(i,ptr,vstart) 8: end if 9: else if (vstart==i) then 10: brek 11: end if 12: end for

Fund cut-set, with edge e8,e9

Bf =[IkB] where I is the unit matrix. Similarly from the Fundamental cut-set matrix, it can be observed that,it is of form

C. Apriory Analysis Cf =[CkI]

The algorithm contain the following modules

and that could be generated as an orthogonal matrix to the fundamental circuit matrix. M = [B T kI] k k1 k2 Cf = k3 k4 k5

e3 1 1 0 0 0

•

•

e4 1 1 1 0 0

e7 0 0 1 1 0

e9 0 0 1 1 1

e1 1 0 0 0 0

e2 0 1 0 0 0

e5 0 0 1 0 0

e6 0 0 0 1 0

e8 0 0 0 0 1

If a fundamental circuit has rows of number of chords the fundamental cut-set will have number of branches as number of rows.

•

•

Generation of spanning tree This takes the time complexity of O(n2 ),where n is the number of vertices. Creation Of Fundamental Circuits This also takes of O(n) since it is checking the spanning tree with a cycle. Creation of Fundamental Cut-set. This involves majorly two loops with number of branch and number of edges.Hence the total time complexity is O(rank X edges) Checking, if the fundamental circuit and fundamental cut-set is having even number of edges. This takes the time complexity f O(n) since it is just checking which bits are reset after ring-

Algorithm 3 create fundcutset by fundckt(int Algorithm 5 check orthogonal(int **BFT,int **BF,int brch,int edg) **CF,int m1,int n1,int m2,int n2) if (n1==m2) then This loop is to initialize the matrix for (i=1;i <= m1;i++) do for (i=1;i<=brach;i++) do for (j=1;j <= n2;j++) do 3: for (j=1;j<=edg;j++) do g resmatrix[i][j]=0 g csmatrix[i][j]=0 5: for (k=1;k <= n1;k++) do end for g resmatrix[i][j]= 6: end for g resmatrix[i][j]+BFT[i][k] * this loop is to hold the transposed ’B’ part of CF[k][j] BF matrix. if (g resmatrix[i][j] mod 2) then for (i=1;i<=(edg-brach);i++) do error,break 9: k=1 end if for (j=(edg-brch+1);j<=edg;j++) do 10: end for g csmatrix[k][l] = g Bf[i][j] end for 12: k =k+1 end for end for end if l =l+1 return 15: end for this loop is to fill the identity part of the CF matrix. i=1 O(edgesXrankXnullity) since the usual 18: for (j=(edg-brch+1);j<=edg;j++) do matrix multiplication involves three loops. g csmatrix[i][j] = 1 i=i+1 D. Experimental Analysis 21: end for The experiment is done by generating Fundamental Circuit matrix and then deducing the FunAlgorithm 4 check evennum common edjes(int damental Cut-set matrix out of it. Then a specific *cktrow,int *cutsetrow,int br) row from the Fundamental Cut-set matrix with ctr=0 respect to a branch is chosen and from the Funfor (i=1;i <= br;i++) do damental Circuit matrix those in which the same g reseven[i]=cktrow[i]ˆcutsetrow[i] branch is set to 1 is ed on to the routine 4: if (cutsetrow[i]==1) && g reseven[i]==0) (check evennum common edjes) one by one for then testing. The counter will be 0 under mod 2 if even ctr++ number of branches are present. To check, if both end if transpose of Fundamental Circuit matrix and Fundaend for mental cut-set matrix are orthogonal, the transpose 8: if (ctr mod 2) then of Fundamental Circuit matrix is generated and it relation proved is multiplied with the Fundamental cut-set matrix end if and each element is checked if 0 under mod 2. If so they are orthogonal. The out put of the program sum operation. The Fundamental Circuit matrix • generating the transpose of the Fundamental 1001101 Circuit matrix. 0100101 The time complexity is O(nullity X edges) • Checking, if the transpose of fundamental 0 0 1 0 0 1 1 circuit matrix and fundamental cut-set matrix are orthogonal. The Fundamental Cut-set Matrix This takes the time complexity of 1 0 0 1 0 0 0

1100100 0010010 1110001 The reduced matrix 1001000 1100100 0010010 The resulting matrix multiplication under mod 2 which is reduced 1001000 1100100 0010010 1001000 0101100 0010010 0111110

1 0 1 0 0 0 1

The corrected matrix for mod 2. 1 0 0 1 0 0 0 100100 010010 001000 101100 010010 111110 110110

The ringsum of 1100100 from the cutset matrix and 0100101 ctr=2. III. C ONCLUSION The test for finding the relation between fundamental circuit and fundamental cut-set mainly involves •

•

finding the ringsum of few rows of each with the time complexity of O(edges) and an additional array to hold the result finding the multiplication of transpose of Bf and Cf is 0 under mod 2 takes the time complexity of O(edges X rank X nullity) but few more two dimensional arrays to hold the resulting matrix and reduced matrices. R EFERENCES

[1] N.Christofides Graph Theory An Algorithmic Approach. demic Press Inc(London)ltd,1975 [2] N.Deo. Graph Theory. PHI,1974

Aca-