Science Journal of Applied Mathematics and Statistics
Volume 5, Issue 1, February 2017, Pages: 10-14

The Best Spanning Tree of Heterogeneous Node Weighted Graphs

Nana Wang1, *, Wei Liu1, 2

1Transportation Management College, Dalian Maritime University, Dalian, China

2Department of Mathematics, Dalian Maritime University, Dalian, China

(Nana Wang)
(Wei Liu)

*Corresponding author

Nana Wang, Wei Liu. The Best Spanning Tree of Heterogeneous Node Weighted Graphs. Science Journal of Applied Mathematics and Statistics. Vol. 5, No. 1, 2017, pp. 10-14. doi: 10.11648/j.sjams.20170501.12

Received: December 22, 2016; Accepted: January 14, 2017; Published: January 17, 2017

Abstract: Minimum spanning tree theory has a wide application in many fields. But in many practical problems, we are often faced with the heterogeneous node weighted graph with both edge weight and node weight be considered. In this paper, we present the definition and the mathematical model of the best spanning tree, then raise an algorithm of the best spanning tree, finally, prove that the algorithm is effective in the best spanning tree problem through an application example.

Keywords: Heterogeneous Node, The Best Spanning Tree, Algorithm, Reduced Graph

Contents

1. Introduction

The minimum spanning tree weighted graph problem has algorithm; reduced graph algorithm; reduced graph a strong practical application background. In a given undirected graph , where  is called node set, which presents several objects involved in this study, is called edge set, which presents the relationship between the objects. The algorithm of solving minimum spanning tree is mainly Kruskal algorithm [1], Prim algorithm [2], Sollin algorithm [3] and Destroying loop rule [4]. In general, the minimum spanning tree solved is not the only one, in other word, the minimum spanning tree appears in multiple ways. Yanxin Qin [5] gives all of the algorithm of solving the minimum spanning tree with the destroying loop rule. When MST increases more constraints or the original problem has many targets, the corresponding issue can be converted into a MST problem of solving the problem of the minimum spanning tree [6]. Zhou and Gen [7] proposed an algorithm which can be applied to solve the multi-criteria minimum spanning tree problem. Guolong Chen et al [8] improved the algorithm of solving the multi-criteria minimum spanning tree problem. Kennedy and Eberhart [9] proposed a binary PSO algorithm to solve the discrete problem. LI Feng, et al [10] proposed the Panic Spreading on the Complicated Network of Heterogeneous Nodes Under Public Crisis. R. H. Heiberger [11] proposed the stock network stability in times of crisis. A. Q. Abbasi and W. A. Loun [12] proposed the symbolic time series analysis of temporal gait dynamics. J. G. Brida, et al [13] proposed the Network analysis of returns and volume trading in stock markets. Sun [14] propose the research degree-Constrained minimum spanning tree problem based on prim algorithm. Torkestani J A [15] propose the degree constrained minimum spanning tree problem: a learning automata approach. WANG [16] propose the label propagation through minimum cost path. Kim K H, Choi S [17] propose the label Propagation through minimax paths for scalable sctni-supervised learning. LIU Jian-Wei, et al [18] propose Semi-supervised Learning methods

We take the following undirected weighted graph as an example

Figure 1. Undirected weighted graph G.

In this article, the destroying rule is used to solve all minimum spanning trees in graph G, shown in Fig 2:

minimum spanning tree (a)

minimum spanning tree (b)

minimum spanning tree (c)

minimum spanning tree (d)

Figure 2. Four minimum spanning trees of graph G.

Now, we have a question: Is there difference between the four minimum spanning trees in the real world on earth? Focus that, they are all minimum spanning trees, only different in structure, however, it is the distinction that leads to different assessment. For example, when the 6 points in this weighted graph G stands for 6 construction sites to build the communication network, the 4 minimum spanning trees in Fig 2 are 4 feasible programs and their vertex degree are all 10, still different in structure. Comparing with the minimum spanning tree (a) and (b), we can find that the connecting way of node is different. For example, in (a), the node v4 connects with 3 edges and the node v5 connects with 1 edge; while in (b), the node v4 links to 2 edges and the node v5 also links to 2 edges. We guess that if the degree of node presents the number of equipments to be installed, it is equal that the investment demand becomes different in node v4 and v5. It also means that the programs of (a) and (b) respectively presents are two types, what’s more, the construction cost they produce is distinguishing. Actually, except the heterogeneity between the nodes of the communication network construction in our daily life, there are many node heterogeneity problems in a variety of backgrounds. Such as logistics network, with different function in different logistics distribution center(node), the cost of every unit is variable. That is to say the nodes are heterogeneous. So when we construct a high efficiency logistics network, we should both consider the logistics fee of the "edge", and the spending of every node. Such that, we are faced with a new problem, if in a weighted graph(edge weighted graph) every node has variable properties, it also means a heterogeneous node network. Aiming at this heterogeneous node network with both edge weight and node weight, we study and propose the problem of the best spanning tree of heterogeneous node weighted graph with considering the influence both brought, and present the definition and the mathematical model of the best spanning tree, and raise a algorithm for the best spanning tree, finally, prove that the algorithm is effective in the best spanning tree problem through an application example. Compare with algorithm of finding all minimum spanning trees by breaking loop, algorithm of the minimum spanning tree. Not only consider the edge right at the same time to consider the right point, so not only more practical significance, but also to promote network optimization and improve efficiency.

2. The Best Spanning Tree of Heterogeneous Node Weighted Graph

2.1. Reled Concepts

(1)   node degree: the number of edges nodes connect.

(2)   node weight:

In a given undirected graph , where ,  and  are remarked as before, what’s more, we increase the node weight. For every node  in G, respectively exists a number , then we call  the node weight of the node . And  varies when the node degree varies. Of course, the node weight  of the node  is also different for each heterogeneous node.

(3)   The best spanning tree

If  is a spanning tree of  we call the minimum spanning tree which has the minimum sum of node weight in the best spanning tree. The expression is given by:

2.2. Algorithm

Step 1: Solve the minimum spanning tree  ith the Kruskal algorithm.

Step2: Identify the reduced graph

(1)   Let  be a branch set,

(2)   Put  into , to form a basic circuit , if  is the only longest edge in the basic circuit , delete it, if not, let  stay in graph .

(3)   , if is smaller and equal to , return to (2)

(4)   Output the reduced graph

Step 3: Identify the fixed edge(save the only shortest edge in the basic cut set)

(1)   Let  be the branch set of the minimum spanning tree , then identify the basic cut set of the branch  in the reduced graph ,. .

(2)   If  is the only shortest edge in the basic cut set , let  be the fixed edge, and remark it with .

(3)   , if  is smaller and equal to , return to (2)

Step 4: Solve switching-in edge(if there is a remark in the basic cut set, it’s a fixed edge, if not, solve switching-in edge in it)

(1)   Let H be a set of switching-in edge and F be a set of switching-out edge, the initial H and F are both empty, ;

(2)   If there is a remark in the basic cut set  of ,  is a fixed edge, then implement (8);

(3)   If there is no remark in the basic cut set  of , put  into ;.

(4)   Let ;

(5)   If  and , put  into ;

(6)

(7)   If  ( is the length of , it is also the number of the elements), return to (5).

(8)   , if , return to (2).

Step 5: The algorithm of the best spanning tree

Let  be a set of switching-in edge and  be a set of switching-out edge. and the function of node weight of each node is .

(1)   If  is empty, the minimum spanning tree is the best spanning tree, output  and respective , and calculate

(2)

(3)

(4)   If  and , with  instead of in , output  and respective , and calculate

(5)   If ,

(6)   If , If , repeat the step (4).

(7)   If , if , repeat the step (4).

(8)   If , if , then return to (3).

(9)   end

3. Application Examples

We take the graph G mentioned before for example, and expand it to a heterogeneous node weighted graph. In this text, the node weight defined is a linear function of node degree, , where  presents the quantitative index of the corresponding edge at the node vi, whose significance is that it’s the metric standard when  at the node . , We take the graph G mentioned before for example, and expand it to a heterogeneous node weighted graph:

Figure 3. The heterogeneous node weighted graph .

Follow the given algorithm of the best spanning tree

(1)   Solve the minimum spanning tree  of graph , and the edge weight is 24, the node weight is 39. This is given by Fig 4:

Figure 4. The minimum spanning tree .

(2)   According to the thought of the destroying loop rule, delete the only longest branch edge in the basic circuit, to get the reduced graph . In the undirected graph , delete the edge  whose weight is 8, the only longest edge in the basic circuit . As same, delete the only longest edge  with weight 4 in the basic circuit . Finally, we identify the reduced graph , shown in Fig 5:

Figure 5. The reduced graph .

(3)   After reducing the undirected graph G, solve the basic cut set of each edge in the minimum spanning tree . The basic cut set is a minimum branch set which separate the connected graph into two parts, one is that there is only one branch of the minimum spanning tree, the others are connected branches. ;  is the only shortest edge and is taken for the fixed edge, then remark the cut set. In , we take the fixed edge , such that, the other minimum spanning tree are just in  and . then we get switching-in edge  and switching-out edge  according to the algorithm.

(4)   When , change  with , then we can get the spanning tree:

Figure 6. The spanning tree of  instead of .

Whose edge weight is 24 and node weight is 40;

change with , we can get the spanning tree:

Figure 7. The spanning tree of instead of .

whose edge weight is 24 and node weight is 40;

When k=2, we can get the spanning tree:

Figure. 8. The spanning tree of k=2.

whose edge weight is 24 and node weight is 41;

Finally, the best spanning tree we get is:

Figure 9. The best spanning tree

The minimum sum of weight of the best spanning tree is 63. Analysing the calculation result, the best spanning tree we defined fully considers both "edge weight" and "node weight", the two factors and their interaction. So the best plan may be not the minimum spanning tree only considers edge weight.

4. Conclusion

This paper gives different numbers to the heterogeneous node from a quantitative point of view, comprehensively considering the weighted graph with both edge weight and node weight. Through reducing the connected graph, solve all the minimum spanning tree with all the minimum of the node weights considered. Then select out the minimum spanning tree which has the smallest node weight, that is the best spanning tree. This thesis just take into account the linear relationship between the node weight and the node degree. As far other circum stances, other function the node weight and the node degree follow or different dimensions they belong to, will be shown in the following papers.

Acknowledgements

This research was supported by Grant 2015020033 from Natural Science Foundation of Liaoning Province of China, for which the authors are grateful.

References

1. Kruskal J. On the Shortest Spanning Subtree of a Graph and theTraveling Sales Man Problem [J]. Proceedings of the AMS, 1956, 7 (1): 48-50.
2. PrimRC. Shortest Connection Networks and Some Generations [J]. Bell System Technical Journal, 1957, 36 (6): 1389-1401.
3. Sollin M, LeTracede Canalisation. Programming, Games, and Transportation Networks [M]. New York, USA: John Wiley & Sons, Inc., 1965.
4. LONG Ya. Research of Algorithm of Constructing Minimum Spanning Tree by Destroying Loop Rule. Journal of Bijie University. 2007 (4): 108-111.
5. QIN Yanxin, WANG Yueguang. Algorithm of Finding all Minimum Spanning Trees by Breaking Loop. Journal of Air Force Radar Academy. 2006 (6), 135-137.
6. GUO Wenzhong, CHEN Guolong. An Efficient Discrete Particle Swarm Optimization Algorithm for Multi-Criteria Minimum Spanning Tree. PR & AI. 2009 (8): 597-604.
7. Zhou Gengui, Gen M. Genetic Algorithm Approach on Multi-Criteria Minimum Spanning Tree. European Journal of Operational Research. 1999, 114 (1): 141-152.
8. CHEN Guolong, GUO Wenzhong etc. An Improved Algorithm to Solve the Multi-Criteria Minimum Spanning Tree Problem. Journal of Software 2006. 364-370.
9. Kennedy. IEberhart R C. A Discrete Binary Version of the Particle Swarm Optimization Algorithm // Proc of IEEE International Conference on Systems Man and Cybemetics Orlando USA, 1997(2)4104-4109.
10. LI Feng, SHEN Huizhang, LI Li. The Panic Spreading on the Complicated Network of Heterogeneous Nodes Under Public Crisis. Mathematics in Practice and Theory. 2013 (1), 97-107.
11. R. H. Heiberger, Stock network stability in times of crisis, Physica A, 2014 (393): 376–381.
12. A. Q. Abbasi, W. A. Loun, Symbolic time series analysis of temporal gait dynamics, J. Signal Process. Syst. 2014 (74): 417–422.
13. J. G. Brida, D. Matesanz, M. N. Seijas, Network analysis of returns and volume trading in stock markets: The Euro Stoxx case, Physica A.2016 (444): 751–764.
14. SUN Xiaojun. Research Degree-Constrained Minimum Spanning Tree Problem Based on Prim Algorithm.Journal of Inner Mongolia Nortnal University. 2016, 45 (4), 445-448.
15. Torkestani J A. Degree Constrained Minimum Spanning Tree Problem: a Learning Automata Approach. Journal of Supercomputing, 2013, 64 (1): 226-249.
16. WANG Xi-li, LIN Hong-Shuai. Label Propagation Through Minimum Cost Path. Chinese Journal of Computers, 2016, 39 (7): 1407-1416.
17. Kim K H, Choi S. Label Propagation through minimax paths for scalable sctni-supervised learning, Pattern Pccognition letters, 2014, 45 (11): 17-25.
18. LIU Jian-Wei, Liu Yuan, LUO Xiong-Lin. Sctni-supervised Learning methods. Chinese Journal of Computers, 2015, 38 (8): 1592-1617.

 Contents 1. 2. 2.1. 2.2. 3. 4.
Article Tools