### Paper Menu >>

### Journal Menu >>

Wireless Sensor Network, 2010, 2, 31-36 doi:10.4236/wsn.2010.21004 anuary 2010 (http://www.SciRP.org/journal/wsn/). Copyright © 2010 SciRes. WSN Published Online J Realization of the Linear Tree that Corresponds to a Fundamental Loop Matrix Jianping QIAN1, Peng-Yung WOO2 1Department of Automation, Nanjing University of Science and Technology, Nanjing, China 2Department of Electrical Engineering, Northern Illinois University, Dekalb, USA Email: pwoo@niu.edu Received October 13, 2009; revised O ctober 27, 2009; acce pted October 28, 2009 Abstract Graph realization from a matrix is an important topic in network topology. This paper presents an algorithm for the realization of a linear tree based on the study of the properties of the number of the single-link loops that are incident to each tree branch in the fundamental loop matrix Bf. The proposed method judges the pendent properties of the tree branches, determines their order one by one and then achieves the realization of the linear tree. The graph that corresponds to Bf is eventually constructed by adding links to the obtained linear tree. The proposed method can be extended for the realization of a general tree. Keywords: Fundamental Loop Matrix, Linear Tree, Graph 1. Introduction Graph realization from a matrix is an important topic in network topology. It has a broad application in electrical networks, switching networks, linear programming etc. The study of graph realization from a matrix is to judge whether a given matrix can be realized to be a graph. If yes, the method for realization needs to be found so that graph realization for a given matrix can be achieved. There are three aspects in graph realization from a matrix: a) the realizablity of the given matrix, b) the method for graph realization from a matrix, c) the unique corre- spondence between the realized graph and the given ma- trix. All the above issues have been under research by using algebra theory, graph theory, geometry structure etc [1–5]. While the necessary and sufficient conditions for the realizability of a graph from a matrix are pro- posed by many researchers from different viewpoints, the judgment of the realizability and th e realization of the graph, in practice, are carried out simultaneously rather than in sequence. Quite a few researchers studied the realization of a linear tree [6,7]. This paper presents an algorithm for the realization of a linear tree based on the study of the properties of the number of the sing le-link loops that are incident to each tree branch in the fundamental loop ma- trix Bf. The proposed method judges the pendent proper- ties of the tree branches, determines their order one by one and then achieves the realization of the linear tree. Since a general tree possesses a linear sub-tree, a general tree can then be realized by adding other tree branches after the linear sub-tree is realized. Th e graph that co rre- sponds to an arbitrary fundamental loop matrix Bf is eventually constructed by adding links to the obtained linear tree. As is seen, the proposed method is simple, practical and efficient in realizing a general tree. 2. Pretreatment For a graph that possesses n nodes and b branches, after a certain tree T is chosen, the fundamental loop matrix Bf has a standard form [Bt 1] where Bt is a (b-n+1)(n-1) matrix. Assume that the columns b1, b2, …, bn-1 in Bt correspond to the branches t1, t2, …, tn-1 of T, while the columns bn, bn+ 1, …, bb in 1 correspond to the links. As is known, biT bj indicates the number of the pairs of corre- sponding entries being all “1”s in the branch columns bi and bj. By realizing a graph from the matrix that is con- structed by the rows of the aforementioned pairs as well as the same indexed rows in the corresponding link col- umns, we know that biT bj is the number of the sin- gle-link loops that pass ti and tj. Specially, biT bi indicates the number of entries “1” in bi. By realizing a graph from the matrix that is constructed by the rows of the afore- mentioned “1”s as well as the same indexed rows in the corresponding link columns, we know that biT bi is the number of the single-link loops that pass ti. To facilitate J. P. QIAN ET AL. 32 our discussions, it is assumed that the tree that corre- sponds to Bt is a linear tree. For example: 123456 4111100 [, ]5110010 60 1 1001 BB1 ft The number of the pairs of corresponding entries be- ing all “1”s in b1 and b2 (i.e., row 1 and row 2) is 2. Thus, b1T b2 =2. By realizing a graph (Figure 1) from the matrix that is constructed by the rows of the aforementioned pairs as well as the same indexed rows in the corresponding link columns, we know that b1T b2=2 is the number of the single-link loops that pass t1 and t2. Specially, b1T b1=2 is the number of the single-link loop s that pass t1. The following theorems present the rela- tionship among the branches of T (Due to limitation of space, the proofs are not presented in this article). 1245 41 110 51 101 Theorem 1: Suppose Bt is a (b-n+1)3 matrix and tp is a pendent branch of the linear tree T that corresponds to Bt. If and only if bpT bq bpT br (pqr, p, q, r=1, 2, 3), the order of the branches of T is tp, tq, tr. As is seen in Figure 2, while there is only one sin- gle-link loop passing tp and tq, there are two passing tp and tr. Therefore, bpT br bpT bq and the order of the branches of T is tp, tr, tq according to Theorem 1. Figure 1. The explanation of b·bj. Figure 2. The explanation of Theorem 1. Theorem 2: Suppose Bt is a (b-n+1)(n-1) matrix and tp is a pendent branch of the linear tree T that corre- sponds to Bt. If and only if bpT bqbpT br (pqr, 1p, q, rn-1), the order of the branches of T is tp, …, tq, …, tr (i.e., tq is closer to tp than tr is). Theorem 3: Suppose Bt is a (b-n+1)(n-1) matrix. For a certain column bl arbitrarily chosen, if blT bp = blT bi (pl, 1pn-1), tp is a pendent branch of the linear tree T that corresponds to Bt. min 1,...2,1, l Theorem 4: Suppose Bt is a (b-n+1)(n-1) matrix. For a certain column bl arbitrarily chosen, if blT bj = blT bi where jU={p, q, r, …, w} (pqr…wl, 1p, q, r, …, wn-1), there must exist a certain sU such that ts is a pendent branch of the linear tree T that corresponds to Bt. min 1,...2,1, l As is seen in Figure 3, while blT bm=blT bn=2, blT bp =blT bq=1. Thus, there must exist a certain sU={p, q} such that tp or tq is a pendent branch of the linear tree T. Theorem 5: Suppose Bt is a (b-n+1)(n-1) matrix. For a certain column bl arbitrarily chosen, if blT bj = blT bi where jU={p, q, r, …, w} (pqr…wl, 1p, q, r, …, wn-1), then the th, tm, tn, …, tl that correspond to ={h, m, n, …, l}construct a linear sub-tree of T, where U = and U = n-1. min 1,...2,1, l U U U As is seen in Figure 3, U ={p, q} and ={m, n, l}. Since blT bm=blT bn=2 but blT bp =blT bq=1, tm, tn and tl construct a linear sub-tree of T. U Theorem 6: Suppose Bt is a (b-n+1)(n-1) matrix. For a certain column bl arbitrarily chosen, blT bj = blT bi where jU={p, q, r, …, w} (pqr…wl, 1p, q, r, …, wn-1). Thus, the th, tm, tn, …, tl that correspond to ={h, m, n, …, l} construct min 1,...2,1, l U Figure 3. The explanation of Theorem 4. Copyright © 2010 SciRes. WSN J. P. QIAN ET AL. 33 a linear sub-tree of T, where U = andU = n-1. Then for a certain k , if there are cer- tain s1 and s2 U*U such that , after the links L’s that correspond to in the graph G that corresponds to Bf are deleted, the graph constructed by G1 that corresponds to U* and the graph G2 that corresponds to (U-U*) is a separable graph, where G1 and G2G, G1G2GL=G, G1G2GL= and GL is the graph that corresponds to the links L’s. If G1 and G2 are inseparable graphs, respectively, then G1 and G2 have a common cut-point. U 1 s b max m,h, U b n,..., U 2 s T k T kbb lk T k b U 1 s b As is seen in Figure 4(a), blT bj =1 where jU={p, q, r, w}. Thus, the th, tm, tn, …, tl that correspond to U={h, m, n, l}con struct a linear sub-tree of T. Let k=h U 2 , and s1 and s2U*={p, q}U. Since=3, links 1, 2 and 3 are deleted. The remaining G1 and G2 are separable graphs as shown in Figure 4(b). 1 T ks T kbbbb s From the above facts, it is seen that when the condi- tions in Theorem 6 are satisfied, G1 and G2 are 2-iso- morphic. Therefore, in the ordering of the branches of the linear tree, the branches of the linear sub-tree that corresponds to G1 are first put into order separately, then those of the linear sub-tree that corresponds to G2. The ordering of the branches of the linear tree is now reduced to the ordering of the branches for each linear sub-tree. The solution of th is problem is depending on the follow- ing Theorem 7, where it is assumed that the sub-trees do not form 2-is o morphism. (a) (b) Figure 4. The explanation of Theorem 6. Theorem 7: Suppose Bt is a (b-n+1)(n-1) matrix. For a certain column bl arbitrarily chosen, blT bj = blT bi where jU={p, q, r, …, w}(pqr…wl, 1p, q, r, …, wn-1). Thus, th e th, tm, tn, …, tl that correspond to ={h, m, n, …, l}construct a linear sub-tree of T, where U = and U =n-1. Then for a certain k, if ther e is a certa in sU such that = , is a pendent branch of the linear tree T that corresponds to Bt. min 1,...2,1, l U T k b U min p,j w U T k b U r,...,q, s bs,j j bs t As is seen in Figure 5, U={p, q, r} and ={h, m, n, l}. Let k=h and s=pU. Since and , is a pendent branch of the linear tree T. U 1 U 1 2 q T hp T hbbbb 3 r T hp T hbbbb p t 3. The Algorithm for the Construction of the Linear Tree We propose the following algorithm for the construction of the linear tree T. The thread of thinking is that one of the two pendent branches of T, e.g., tp is found first. The other pendent tree branch tq is found by using tp as a base. Then tq is taken off, the other pendent tree branch tr is found by using tp as a base again. Keep on with this pro- cedure until the order of all the branches of T is decided. 1) For a given fundamental loop matrix Bf=[Bt 1], let M=BtTBt where the entry =. Establish a ma- trix Bt’ which is of the same dimension as Bt so that the columns of Bt after ordering can be put into Bt’. Let the column index for Bt’ be f. Set f=1. ij mji bb T 2) For row i (1in-1) in M (Usually, let i=1 first to follow the row order in M), if there is only one entry mip in row i th a t takes the minimum value, tp that corre- sponds to column p is a pendent branch of the linear tree Figure 5. The explanation of Theorem 7. C opyright © 2010 SciRes. WSN J. P. QIAN ET AL. 34 T according to Theorem 3. Go to step (6). On the other hand, if there are multiple entries , , , …, in row i that take the minimum value, there must exist a certain sUd={pd, qd, rd, …, wd} (d is the iteration index. Let d=1 first.) such that ts that corresponds to column s is a pe ndent branch of the linear tree T accord- d ip md iq md ir m d iw m ing to Theorem 4. 3) For row k in M where k={h, m, n, …, l}(Usually, let k follow the row order in ), if there is only one entry mks in row k that take s th e mi n i mu m v a lu e where sUd, ts that correspond s to column s is a pendent branch of the linear tree T according to Theorem 7. d U d U Go to step (4). On the other hand, if there are multiple en- tries , , , …, in row k that take the minimum value, there mu st exist a certain sUd={pd, qd, rd, …, wd} (d=d+1) such that ts that corresponds to column s is a pe ndent branch of the linear tree T accord- d kp md kq md kr md kw m ing to Theorem 4. Repeat step (3) until k takes all the elements in . At that time, if there are still multiple entries in row k that take the minimum value, go to step (8). d U 4) If the last column of Bt’ is not filled by a column from Bt yet, set p=s. Go to step (6). Otherwise, j udge th e adjacency of tk, ts and tp according to Theorem 2. 5) If tk and tp are at the same side of ts, i.e., the order is ts, …, tk, …, tp, set p=s. Go to step (6). On the other hand, if tk and tp are at the different sides of ts, i.e., the order is tk, …, ts, …, tp, use tk as a pendent tree branch to find the order of the tree branches corresponding to Ud and put them into the co lumns of Bt’, i.e., column f to column f’ where f’=f+(number of elements in Ud)-1. Set all the entries in the columns of M corresponding to Ud to be . If the entries in M are all , stop. If not, set f = f+ (number of elements in Ud). Go back to step (2). 6) If the last column of Bt’ is already filled by a col- umn from Bt, i.e., a pendent tree branch at one end is already decided, go to step (b). Otherwise a) As sume the p endent br anch of T is tp. Put tp into the last column of Bt’. Set i=p. Go to step (7). b) Put column p of Bt into column f of Bt’. Set f=f+1. 7) If all the columns of Bt have been put into Bt’, the ordered columns of Bt’ have already constitute a linear tree. Stop. Otherwise, set the entries in column p of M to be . Go back to step (2). 8) When there are only two entries in Ud, choose ar- bitrar i ly sUd. ts is a pendent branch of T. Go to step (4). Otherwise, according to Theorem 5 and Theorem 6, the linear sub-tree in graph G1 that corresponds to Ud*=Ud can be put into order separately. Thus, take the columns Bt(1) in Bt that correspond to the elements in Ud to construct Bt(1)T Bt(1)=M(1). Repeat steps (2)-(8) for M(1). If the number of elements in Ud is not changed after one iteration, the order of the corre- sponding tree branches is arbitrary. Put the ordered columns of Bt(1) into column f to column f’ where f’=f+(number of elements in Ud)-1. Set all the en tr ies in the columns of M corresponding to Ud to be . If the entries in M are all , stop. If not, set f=f+(number of elements in Ud). Go back to step (2). 4. An Example Given a fundamental loop matrix Br=, 100011100 010010111 001010001 000111111 987654321 we have Bt =and BtT. 11100 10111 10001 11111 54321 1111 1001 1101 0101 0111 a) According to step (1), M=BtTBt=. 42323 22211 32322 21222 31223 5 4 3 2 1 54321 Also, establish a matrix Bt’ which is of the same di- mension as Bt so that the columns of Bt after ordering can be put into Bt’. Let the column index for Bt’ be f. Set f=1. b) According to step (2), consider row 1 of M. As m14 is the only entry in row 1 that takes the minimum value, t4 is one pendent branch of T. Go to step (6). c) According to step (6)(a), put co lumn 4 of Bt into the last column of Bt’, i.e., Bt’=. Set i=4. 1 0 0 1 4 Copyright © 2010 SciRes. WSN J. P. QIAN ET AL. 35 d) According to step (7), set all the en tries in column 4 of M to be , i.e., M = 4323 2211 3322 2222 3223 5 4 3 2 1 54321 e) According to step (2), consider ro w 4 of M. As m41 and m42 are the entries in row 4 that take the minimum value, there must exist the other pendent branch of T among t 1 and t 2 that correspond to U 1={1, 2}. Here, ={3, 4, 5}. 1 Uf) According to step (3), consider row 3 of M. As m31 and m32 are the entries in row 3 that take the minimum value, there must exist the other pendent branch of T among t 1 and t 2 that correspond to U 2={1, 2}. Here, ={3, 4, 5}. 2 Ug) Repeat step (3). Consider row 5 of M. m52 is the only entry in row 5 th at takes the minimum value. h) According to step (4), as the last column of Bt’ is already filled by a column from Bt, judge the adjacency of t5, t2 and t4. As m42<m45 in m4, the order is t2, …, t5, …, t4. i) According to step (5), as t5 and t4 are at the same side of t2, t2 is the other pendent branch of T that is based on t4. Set p=2. j) Accord ing to step (6)(b) , put colu mn 2 of Bt into th e first column of Bt’, i.e., Bt’=. Set f=1+1=2. 10 01 00 11 42 k) According to step (7), set all the entries in colu mn 2 of M to be , i.e., M =. 433 221 332 222 323 5 4 3 2 1 54321 l) According to step (2), consider row 4 of M. As m41 is the only entry in row 4 that takes the minimum value, t1 is the other pendent branch of T that is based on t4 with t2 taken off. m) According to step (6), put column 1 of Bt into the second column of Bt’, i.e., Bt’=. Set f=2+1=3. 100 011 010 111 412 n) According to step (7), set all the entries in colu mn 1 of M to be , i.e., M =. 43 22 33 22 32 5 4 3 2 1 54 321 o) According to step (2), consider row 4 of M. As m43 and m45 are the entries in row 4 that take the minimum value, there must exist the other p endent branch of T that is based on t4 with t1 and t2 taken off among t3 and t5 that correspond to U1={3, 5}. Here, ={1, 2, 4}. 1 U p) According to step (3), consider row 1 of M. m13 is the only entry in row 1 that takes the minimum value. q) According to step (4), as the last column of Bt’ is already filled by a column from Bt, judge the adjacency of t1, t3 and t4. As m13>m14 in m1, the order is t1, …, t3, …, t4. r) According to step (5), as t1 and t4 are at the different sides of t3, t2 is used as the other pendent branch of T to find the order of the tree branches corresponding to Ud. Put column 3 of Bt into the fourth (f’=3+2-1=4) column of Bt’, i.e., Bt’=. 1100 0111 0010 1111 4312 Set f=3+1=4. Set all the en tries in column 3 of M to be , i.e., M =. 4 2 3 2 3 5 4 3 2 1 54321 s) According to step (2), consider row 4 of M. As m45 is the only entry in row 4 that takes the minimum value, t5 is the other pendent branch of T that is based on t1 with C opyright © 2010 SciRes. WSN J. P. QIAN ET AL. Copyright © 2010 SciRes. WSN 36 5. Conclusions t3 taken off. t) According to step (6), put column 5 of Bt into the third column of Bt’, i.e., Bt’=. Set f=4+1=5. 11100 01111 00110 11111 43512 This paper presents an algorithm for the realization of a linear tree based on the judgment of the pendent proper- ties of the tree branches and the determination of their order one by one. The graph that corresponds to Bf is eventually constructed by adding links to the obtained linear tree. As an arbitrary tree contains a linear tree, the linear tree can then be realized first to realize a general tree. This will be discussed in another paper of ours. u) According to step (7), stop. The main contribution of this paper lies in the p roposi- tion of a new approach to the realization of a linear tree. Experiments validate the effectiveness of the proposed approach. This lays a foundation to the realization of a general tree and therefore a random graph from a given matrix. As a summary, we have the following table to achieve the order of the columns in Bt’. Colu. in Bt’ 5 1 2 4 3 Colu. in Bt 4 2 1 3 5 Steps (b),(c),(d) (e),(f),(g), (h),(i),(j), (k) (l),(m),(n) (o),(p), (q),(r) (s),(t),(u) According to Algorithm Steps (2),(6), (7) (2),(3),(3), (4),(5),(6), (7) (2),(6),(7) (2),(3), (4),(5) (2),(6),(7) 6. References [1] L. Q. Lei and B. Q. Dai, “A convenient method for for- mulation of a node incidence matrix from a basic cutset matrix,” (In Chinese), Journal of Jiangxi Polytechnic University, Vol. 14, No. 3, September 1992. [2] W. Mayeda, “Graph theory,” John Wiley, New York, 1972. The column order [2, 1, 5, 3, 4] of Bt’ is thus the or- der of the branches of the linear tree as shown by the bold segments in Figure 6. The graph that corresponds to Bf can then be obtained by adding the links 6, 7, 8 and 9. [3] K. P. Rajappan, “On Okada’s method for realizing cutset matrices,” Journal of Combinational Theory, Vol. 10, pp. 135–142, 1971. [4] M. N. S. Swamy and K. Thulasiraman, “Graph, network and algorithms,” John Wiley, New York, 1981. [5] L. Zhu, “An expression for the relationship between the incidence Matrix A of Graph G and the basic loop Matrix Bf,” (In Chinese), Teaching and Scientific Technology, No. 1, pp. 72–75, March 1996. [6] R. B. Ash and W. H. Kim, “On realizability of a circuit matrix,” IRE Transactions on Circuit Theory, Vol. CT-6, pp. 219–223, June 1959. [7] S. R. Parker and H. J. Lohse, “A direct procedure for the synthesis of network graphs from a given fundamental loop or cutset matrix,” IEEE Transactions on Circuit The- ory, Vol. CT-16, pp. 221–223, May 1969. Figure 6. The graph that corresponds to Bf. |