Mathematics
The Minimum Spanning Tree Method
The Minimum Spanning Tree (MST) method is a graph theory algorithm used to find the shortest path between nodes in a connected graph. It works by selecting the edges with the lowest weight until all nodes are connected, creating a tree-like structure. The MST method has applications in computer networking, transportation, and logistics.
Written by Perlego with AI-assistance
Related key terms
1 of 5
10 Key excerpts on "The Minimum Spanning Tree Method"
- Shaharuddin Salleh, Zuraida Abal Abas(Authors)
- 2016(Publication Date)
- Chapman and Hall/CRC(Publisher)
133 5 Computing the Minimum Spanning Tree 5.1 Problem Description Every connected graph G ( V , E ) may have several spanning trees. A spanning tree T ( V , E ′ ) is a subgraph, with the criteria that it includes all the nodes of the original graph, V = { v i }, i = 1, 2,… n , and all these nodes are connected by only selected edges E ′ ⊆ E ( G ). Another important criterion of a spanning tree is that no cycle is allowed when selecting the edges. This is in line with the definition of a tree as a connected graph without any cycles [1]. As a rule of thumb, a tree with n nodes will form a spanning tree with only n − 1 edges [2,3]. For example, a cyclic graph with four nodes, as illustrated in Figure 5.1a, has a total of four spanning trees with each formed by three edges, as illustrated in Figure 5.1b. Another example, in Figure 5.2a, is a diamond graph with four nodes, and it has a total of eight spanning trees with each also formed by three edges, as illustrated in Figure 5.2b. Suppose a weight or length is assigned to each of the edges of the graph. The total weight of the resulting spanning tree can be computed by having the summation of all the weights assigned to the selected edges; hence, different total weights could be obtained from these different spanning trees. The problem is to find the minimum spanning tree of a graph. The minimum spanning tree is the spanning tree where the sum of weights on its edges is the minimum given by MST Min x w ij ij ij = ∑ (5.1) Subject to x ij = 1 0 if is selected otherwise e ij for i , j = 1, 2… n . In the above equation, MST is the minimum spanning tree and x ij denotes the decision variable, e ij is the edge, w ij is the weight assigned to e ij , and n is the total num-ber of nodes in the graph. Prim’s algorithm and Kruskal’s algorithm are among the prominent methods used to find the minimum spanning tree. Finding the minimum spanning tree is a very com-mon problem as it has many real-world applications.
eBook - PDF- Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser(Authors)
- 2013(Publication Date)
- Wiley(Publisher)
A tree, such as this, that contains every vertex of a connected graph G is said to be a spanning tree, and the problem of computing a spanning tree T with smallest total weight is known as the minimum spanning tree (or MST) problem. The development of efficient algorithms for the minimum spanning tree prob- lem predates the modern notion of computer science itself. In this section, we discuss two classic algorithms for solving the MST problem. These algorithms are both applications of the greedy method, which, as was discussed briefly in the previous section, is based on choosing objects to join a growing collection by it- eratively picking an object that minimizes some cost function. The first algorithm we discuss is the Prim-Jarn ´ ık algorithm, which grows the MST from a single root vertex, much in the same way as Dijkstra’s shortest-path algorithm. The second algorithm we discuss is Kruskal’s algorithm, which “grows” the MST in clusters by considering edges in nondecreasing order of their weights. In order to simplify the description of the algorithms, we assume, in the follow- ing, that the input graph G is undirected (that is, all its edges are undirected) and simple (that is, it has no self-loops and no parallel edges). Hence, we denote the edges of G as unordered vertex pairs (u, v). Before we discuss the details of these algorithms, however, let us give a crucial fact about minimum spanning trees that forms the basis of the algorithms. 14.7. Minimum Spanning Trees 671 A Crucial Fact about Minimum Spanning Trees The two MST algorithms we discuss are based on the greedy method, which in this case depends crucially on the following fact. (See Figure 14.19.) V 1 V 2 e min-weight “bridge” edge e Belongs to a Minimum Spanning Tree Figure 14.19: An illustration of the crucial fact about minimum spanning trees. Proposition 14.25: Let G be a weighted connected graph, and let V 1 and V 2 be a partition of the vertices of G into two disjoint nonempty sets.
eBook - PDFData Structure Practice
for Collegiate Programming Contests and Education
- Yonghui Wu, Jiande Wang(Authors)
- 2016(Publication Date)
- CRC Press(Publisher)
405 Chapter 12 Algorithms of Minimum Spanning Trees A tree is a connected undirected simple graph with no circuit. A tree with n vertices has n – 1 edges. If an edge of a tree is deleted, the tree becomes an unconnected graph. If an edge is added between any two vertices in a tree, a circuit is produced. As mentioned, breadth-first search (BFS) or depth-first search (DFS) for a connected graph will produce a BFS tree or a DFS tree. In this chapter, we focus on finding a spanning tree so that the sum of weights of edges of the tree is minimized in a weighted undirected connected graph. Such a spanning tree is called a minimum spanning tree (MST). The greedy strategy is used to find an MST. That is, at each step, the added edge can’t form a circuit, and based on it, the weight of the added edge should be minimal. Such an added edge is called a safe edge. There are two algorithms of MSTs: 1. Kruskal algorithm 2. Prim algorithm The two algorithms get an MST by different methods. 12.1 Kruskal Algorithm Initially, n vertices constitute a forest. Then, edge ( u , v ) connecting two distinct trees in the forest with the least weight is regarded as the safe edge and is added to the forest. Repeat the process until the MST is obtained. Based on it, given a weighted connected graph G ( V , E ), where | V | = n and | E | = m , Kruskal algorithm is as follows: Sort edges in ascending order of weight values; Suppose initially F is a forest consisting of n trees, and each tree corresponds to a vertex in graph G ; Initially the sum of weights of edges of the minimum spanning tree ans = 0;
eBook - PDF- Michael T. Goodrich, Roberto Tamassia(Authors)
- 2014(Publication Date)
- Wiley(Publisher)
442 Chapter 15. Minimum Spanning Trees minimum spanning tree, T , for G, to decide which of the m edges in G to lease. Suppose now that it is time renew the leases for connecting the vertices in G and you notice that the rent for one of the connections not used in T has gone down. That is, the weight, w(e), of an edge in G that is not in T has been reduced. De- scribe an O(n +m)-time algorithm to update T to find a new minimum spanning, T , for G given the change in weight for the edge e. A-15.5 Consider a scenario where you have a set of n players in a multiplayer game that we would like to connect to form a team. You are given a connected, weighted, undirected graph, G, with n vertices and m edges, which represents the n players and the m possible connections that can be made to link them together in a com- municating team (that is, a connected subgraph of G). In this case, the weight on each edge, e, in G is an integer in the range [1, n 2 ], which represents the amount of game points required to use the edge e for communication. Describe how to find a minimum spanning tree for G and thereby form this team with mini- mum cost, using an algorithm that runs in O(m α(n)) time, where α(n) is the slow-growing inverse of the Ackermann function. A-15.6 Suppose you have n rooms that you would like to connect in a communication network in one of the dormitories of Flash University. You have modeled the problem using a connected, undirected graph, G, where each of the n vertices in G is a room and each of the m edges in G is a possible connection that you can form by running a cable between the rooms represented by the end vertices of that edge. In this case, however, there are only two kinds of cables that you may possibly use, a 12-foot cable, which costs $10 and is sufficient to connect some pairs of rooms, and a 50-foot cable, which costs $30 and can be used to connect pairs of rooms that are farther apart.
eBook - PDF- Peter Grossman(Author)
- 2017(Publication Date)
- Red Globe Press(Publisher)
As a first step towards solving the problem, we can look for some properties that the solution must have. The solution is itself a graph, consisting of all of the vertices but only some of the edges of the original weighted graph. Clearly the solution must be a connected graph, in order to ensure that any two sites can communicate with each other. Furthermore, since the solution represents the cheapest possible network connecting the sites, it cannot contain any cycles because if a cycle were present, then one of the edges in the cycle could be removed to produce a connected graph with a smaller total weight. We can sum up these observations as follows. The solution to the problem must be a tree. The vertices of the tree must be the vertices of the original graph, and the edges of the tree must be selected from the set of edges in the original graph. A tree that satisfies these requirements is called a spanning tree of the graph. Typically, a connected graph has many spanning trees. In Figure 11.3, not only do the edges CD , BC and AC form a spanning tree, but so do the edges AB , AC and AD , and the edges AB , BC and CD . The problem is to find a spanning tree with the smallest possible total weight, since this will represent the cheapest possible network. A spanning tree with this property is called a minimal spanning tree . Here, then, is the problem stated in the terminology of graph theory. Minimal Spanning Tree Problem Design an algorithm that inputs a connected weighted graph and outputs a minimal spanning tree for the graph. 209 11 Trees Figure 11.3 spanning tree How might we go about finding a minimal spanning tree? A plausible approach would be to start at one of the vertices, and pick an edge with the least weight of all the edges incident to that vertex. This edge forms the start of our minimal spanning tree. Next, we could look for an edge with least weight of all the edges that join up with the edge we already have.
eBook - ePub- James Evans(Author)
- 2017(Publication Date)
- CRC Press(Publisher)
Fig. 3.2 , the maximum spanning tree is given by the edges (3, 4), (2, 4), (1, 2), and (4, 5). The maximum capacity on the route from vertex 1 to vertex 5 is 5; from vertex 2 to vertex 3, it is 7, and so on.3.3 Variations of the Minimum Spanning Tree Problem
Many variations of the minimum spanning tree problem have been proposed and investigated. These typically involve adding restrictions on the structure of feasible solutions. In this section we briefly review some of these variations. The reader is referred to the references for more detail about these problems and algorithms for solving them.The Capacitated Minimum Spanning Tree (Chandy and Lo, 1973)
The capacitated minimum spanning tree problem involves finding a spanning tree on a flow network that has applications in the design of teleprocessing networks. We are given an undirected graph G = (X, E ) with cost d (x, y ) and capacity c (x, y ) associated with edge (x, y ). One of the vertices is a sink; the rest are sources. Each source i has a supply a (i ), and the sink has a demand equal to the sum of all supplies. The problem is to find a spanning tree in which all flow goes from the sources to the sink only along the edges of the tree at minimum cost and subject to the capacity constraints and, of course, conservation of flow. Fig. 3.5 shows an example for which the minimum spanning tree results in an infeasible solution. Figure 3.6 gives the optimal solution. No efficient algorithm is known for the general problem; thus heuristics must be used.Degree-Constrained Spanning Trees (Gabow, 1978; Glover and Klingman, 1974)
Many applications of spanning trees occur in computer and communication networks. Many of these problems have constraints restricting the number of edges that are allowed to be incident to a vertex. For example, one vertex might represent a central computing site. The other vertices might represent terminals which must be linked to the central site by cable paths. If we restrict the number of edges incident to the central site vertex to b, this guarantees that the computer’s load is spread over b
eBook - PDFGeneralized Network Design Problems
Modeling and Optimization
- Petrica C. Pop(Author)
- 2012(Publication Date)
- De Gruyter(Publisher)
Chapter 2 The Generalized Minimum Spanning Tree Problem (GMSTP) The minimum spanning tree (MST) problem has a venerable history in the field of combinatorial optimization. The problem was first formulated in 1926 by Boruvka, who is said to have learned about it during the rural electrification of the Southern Moraria, where he provided a solution to find the most economical layout of a power- line network. The importance and popularity of the MST problem stem from several facts: it allows an efficient solution, which makes the problem practical to solve for large graphs. Some polynomial-time algorithms for solving the MST problem were developed by Kruskal [100], Prim [171], Dijkstra [25] and Sollin [189] and have been applied to many combinatorial optimization problems such as transportation prob- lems, telecommunication network design, distribution systems, and so on. However, most attractive to many researchers has been the extension of the MST problem, in the last decade, to e.g., the degree-constrained minimum spanning tree problem (dc-MST) by Narula and Ho [130], the probabilistic minimum spanning tree problem (p-MST) by Bertsimas [11], the stochastic minimum spanning tree problem (s-MST) by Ishii et al. [89], the quadratic minimum spanning tree problem (q-MST) by Xu [204], the minimum Steiner tree (MStT) problem by Maculan [117], the gener- alized minimum spanning tree problem (GMSTP) by Myung, Lee and Tcha [128], etc. The extensions of the MST problem are generally N P -hard problems and therefore polynomial-time solutions do not exist. In this section, we are concerned with the generalized version of the minimum spanning tree problem (MST), called the generalized minimum spanning tree problem (GMSTP). Given an undirected graph, whose nodes are partitioned into a number of subsets (clusters), the GMSTP aims to find a minimum-cost tree, spanning a subset of nodes, which includes exactly one node from each cluster.
- Susanna Epp(Author)
- 2019(Publication Date)
- Cengage Learning EMEA(Publisher)
Example 10.6.3 Copyright 2020 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it. 750 CHAPTER 10 THEORY OF GRAPHS AND TREES As with Kruskal’s algorithm, in order to ensure a unique output, the edges of the graph could be placed in an array and those with the same weight could be added in the order they appear in the array. It is not hard to see that when a connected graph is input to Prim’s algorithm, the result is a spanning tree. What is not so clear is that this spanning tree is a minimum. The proof of the following theorem establishes that it is. Theorem 10.6.3 Correctness of Prim’s Algorithm When a connected, weighted graph G is input to Prim’s algorithm, the output is a minimum spanning tree for G . Proof: Let G be a connected, weighted graph, and suppose G is input to Prim’s algorithm. At each stage of execution of the algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. As long as there are vertices outside the subgraph, the connectedness of G ensures that such an edge can always be found.
eBook - PDF- Sheldon M. Ross(Author)
- 2000(Publication Date)
- Cambridge University Press(Publisher)
In other words, regarding the links built as being edges of a graph connecting the n locations (ver-tices), we desire to construct the cheapest connected graph. Since all costs are positive, it makes no sense to allow any cycles; thus, the cheap-est connected graph will be a tree. The problem of finding the cheapest such tree is known as the minimum spanning tree problem. The greedy algorithm for the minimum spanning tree problem con-structs the edges in sequence as follows: at each stage, build the cheapest edge that – when added to the already constructed graph – does not re-sult in a cycle. 132 Graphs and Trees Figure 5.8: Adding (2, 5), the Cheapest Edge, Would Result in a Cycle Example 5.3a Suppose that the costs for constructing a link between vertices i and j are as follows: 1 2 3 4 5 6 7 8 9 1 3.6 4.8 5.2 2.5 3.9 6.2 7.0 5.4 2 8.1 7.6 3.8 3.7 5.1 4.4 6.2 3 2.4 6.0 5.8 7.7 9.2 10 4 8.0 3.7 6.5 7.0 6.9 5 4.0 5.5 6.6 7.7 6 8.1 8.8 5.9 7 5.7 5.6 8 7.3 The greedy algorithm starts by building the cheapest edge, namely ( 3 , 4 ) at cost 2.4; then the next cheapest, namely ( 1 , 5 ) at cost 2.5; then ( 1 , 2 ) at cost 3.6; then ( 4 , 6 ) at cost 3.7 (choosing among same-priced edges is arbitrary); and then ( 2 , 6 ) at cost 3.7. The next cheapest edge is (2,5); however, since its addition would result in a cycle (see Figure 5.8), it is not included and instead we go on to the next cheapest, and so on until a tree is obtained (see Figure 5.9 for the resulting tree). The Minimum Spanning Tree Problem 133 Figure 5.9: The Minimal Cost Spanning Tree Figure 5.10: Adding an Edge to a Tree; Then Removing an Edge from the Resulting Cycle We will show that the greedy algorithm is optimal. However, before doing so, let us note that if we add a new edge to a tree then the result-ing graph contains a cycle; and if we subsequently delete any edge of this cycle, another tree results (see Figure 5.10). Proposition 5.3.1 The greedy algorithm results in a minimal cost span-ning tree.
eBook - PDFHandbook of Sensor Networks
Compact Wireless and Wired Sensing Systems
- Mohammad Ilyas, Imad Mahgoub, Mohammad Ilyas, Imad Mahgoub(Authors)
- 2004(Publication Date)
- CRC Press(Publisher)
39.2.4 Low-Weight Structures The power stretch factor previously discussed is defined for unicasting communications. However, in practice, it is also necessary to consider broadcast or multicast communications. Wan et al . [151] showed that the minimum energy cost of broadcasting or multicasting is related to the total energy cost of all links in the Euclidean minimum spanning tree, MST . They proved that a broadcasting method based on the Euclidean minimum spanning tree rooted at the sender uses energy no more than 12 times the p v v i h i i ( ) 1 1 Π = = − ∑ β ρ H u v V H G G p u v p u v ( ) ( , ) ( , ) , = ∈ max ρ ρ H V n H n V ( ) ( ). | | = = sup H G ( ) H n ( ) ρ ρ H H G G 1 2 ( ) ( ) ≥ Wireless Sensor Networks and Computational Geometry 39 -7 minimum energy cost of any broadcasting scheme. Therefore, the network topology needs to be a low-weight structure. Given a structure G over a set of points, let ω ( G ) be the total length of the links in G and ω β ( G ) be the total power needed to support all links in G , i.e., . Then, a structure G is called low weight if ω ( G ) is within a constant factor of ω ( MST ). 39.2.5 Geometric Structures Several geometric structures have been studied recently by computational geometry scientists and net-work engineers. Here, we review the definitions of some of them THAT could be used in wireless sensor networking applications are reviewed. Let G = ( V , E ) be a geometric graph defined on vertex set V with edge set E . 39.2.5.1 Minimum Spanning Tree, Relative Neighborhood Graph and Gabriel Graph The minimum spanning tree of G , denoted by MST( G ), is the tree belonging to E that connects all nodes and whose total edge length is minimized. MST( G ) is obviously one of the sparsest connected subgraphs, but its stretch factor can be as large as n – 1. The relative neighborhood graph , denoted by RNG( G ), is a geometric concept proposed by Toussaint [148].
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
