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
To cite this article:
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
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 , Prim algorithm , Sollin algorithm  and Destroying loop rule . 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  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 . Zhou and Gen  proposed an algorithm which can be applied to solve the multi-criteria minimum spanning tree problem. Guolong Chen et al  improved the algorithm of solving the multi-criteria minimum spanning tree problem. Kennedy and Eberhart  proposed a binary PSO algorithm to solve the discrete problem. LI Feng, et al  proposed the Panic Spreading on the Complicated Network of Heterogeneous Nodes Under Public Crisis. R. H. Heiberger  proposed the stock network stability in times of crisis. A. Q. Abbasi and W. A. Loun  proposed the symbolic time series analysis of temporal gait dynamics. J. G. Brida, et al  proposed the Network analysis of returns and volume trading in stock markets. Sun  propose the research degree-Constrained minimum spanning tree problem based on prim algorithm. Torkestani J A  propose the degree constrained minimum spanning tree problem: a learning automata approach. WANG  propose the label propagation through minimum cost path. Kim K H, Choi S  propose the label Propagation through minimax paths for scalable sctni-supervised learning. LIU Jian-Wei, et al  propose Semi-supervised Learning methods
We take the following undirected weighted graph as an example
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)
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:
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 ;
(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
(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).
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:
whose edge weight is 24 and node weight is 41;
Finally, the best spanning tree we get is:
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.
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.
This research was supported by Grant 2015020033 from Natural Science Foundation of Liaoning Province of China, for which the authors are grateful.