Questions and Answers > Colorado Technical University MATH 451-1404B-Minimal Spanning Tree

Colorado Technical University MATH 451-1404B- Minimal Spanning Tree Minimal Spanning Tree Introduction Minimal spanning tree model considers the shortest distance connecting all the nodes together allowing one to m ...

Colorado Technical University MATH 451-1404B- Minimal Spanning Tree Minimal Spanning Tree Introduction Minimal spanning tree model considers the shortest distance connecting all the nodes together allowing one to move from any node to any other node through other nodes. In this section, you will consider an example of this model and solve it graphically. Learning Materials What is minimal-spanning tree model? In a minimal spanning tree model, you are looking for the shortest destine or time, or other measure which connects all the nodes together. Therefore, one can walk from any node to other nodes either directly or through other node(s). Unlike other models, this model does not define nodes as origin, destination, or transshipment nodes. You will try to solve this model through connecting the shortest arc value from any node you decided to start and continue the process until all the unconnected nodes are connected. Figure 1: A Minimal Spanning Tree Network Understanding the Tree Network Start from node A as the origin and continue with the following steps: ·First, you find the shortest distance from node A to the surrounding nodes. Node F is the closest with an arc value of 2. ·Then, you look for the next shortest distance from both nodes A and F in the surrounding nodes. Node E with an arc value of 1 is the only choice. Now connect node F to node E. ·Next, you look for the shortest arc from nodes A, E, and F. The next shortest arc is between nodes A and B with a value of 3. Now connect node A to node B. ·The next node to be the shortest from nodes A, B, E, and F is node H with an arc value of 5. You connect node E to node H. ·The next node is G. You connect node G to node E. ·The next node is I with the arc value of 10. You connect node E to node I. ·The next node closest to any of nodes A, B, E, F, G, H, and I is node D with an arc value of 4. You connect node D to node I. ·The next node is C with an arc value of 8 from node D. You connect node C to node D. ·Finally, node J has the shortest arc from node I and is the last node to be connected. Connecting node J to node I gives the solution. Calculating the Total Distance The total distance is then calculated by adding all these colored red and you get a value of 48. This total is the shortest total distance you can find among other routes if you decide to take. Use the following links to answer the question: Which of the following is an edge that is not included in a minimum spanning tree? 2, 5 1, 2 3, 5 2, 4 Suppose that you have a network with 8 nodes, 1 through 8, with the following links: What is the cost of the highest cost link included in a minimal spanning tree? 6 5 2 4 Suppose that you have a network with 8 nodes, 1 through 8, with the following links: What is the cost of the highest cost link included in a minimal spanning tree? 6 5 2 4 Use the following links to answer the question: What is the total length of a minimum spanning tree? 5 22 12 17 Suppose that you have a network with 8 nodes, 1 through 8, with the following links: What is the total length of the minimal spanning tree? 91 110 87 94 Suppose that you have a network with 8 nodes, 1 through 8, with the following links: Using the algorithm presented in the learning materials and starting with node 7, what are the next 2 nodes added? 6, 5 3, 8, 6, 8 2, 8 Suppose that you have a network with 8 nodes, 1 through 8, with the following links: What is the total cost of the minimum spanning tree? 12 19 29 15 Of all of the links excluded from a minimum spanning tree, what is the lowest cost? 2 1 8 3 What link is not in the minimal spanning tree? 5 10, 15, 6 7 3 Suppose that you have a network of 3 nodes that are all interconnected and with all edges having the same cost. How many distinct minimal spanning trees are there? 3 1 4 0 Suppose that you have a network with 4 nodes and with all of the possible edges (also called the complete graph) having the same cost. How many distinct minimal spanning trees are there? 4 19 16 14