Realization of the Linear Tree that Corresponds to a Fundamental Loop Matrix

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.

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.

Cite this paper

nullJ. QIAN and P. WOO, "Realization of the Linear Tree that Corresponds to a Fundamental Loop Matrix,"*Wireless Sensor Network*, Vol. 2 No. 1, 2010, pp. 31-36. doi: 10.4236/wsn.2010.21004.

nullJ. QIAN and P. WOO, "Realization of the Linear Tree that Corresponds to a Fundamental Loop Matrix,"

References

[1] L. Q. Lei and B. Q. Dai, “A convenient method for formulation 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.

[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 Theory, Vol. CT-16, pp. 221–223, May 1969.

[1] L. Q. Lei and B. Q. Dai, “A convenient method for formulation 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.

[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 Theory, Vol. CT-16, pp. 221–223, May 1969.