NM - Spanning Trees Lesson
Spanning Trees
Adapted from Course materials (VII.B Student Activity Sheet 6-7) for AMDM developed under the leadership of the Charles A. Dana Center, in collaboration with the Texas Association of Supervisors of Mathematics and with funding from Greater Texas Foundation.
High Speed Internet
Your company must run Ethernet cables to five different offices so that all five offices have high-speed Internet access. For each computer to be on the office network, there must be a way to get from each computer to the other computers by following the cable.
One worker proposed running cable between the five offices as illustrated in the following diagram. The vertices represent the offices, and the edges represent segments of cable.
How many lengths of cable (edges) are used?
8 lengths of cables are used
Explain why this is an inefficient way to run the cable.
This is inefficient because the office in the upper left, for example,
is connected to the office in the lower right in more than one way, thereby using more cable than necessary.
Can you design a more efficient network and indicate how many lengths of cable are used?
Yes, every efficient network only needs four lengths of cable(edges).
Graph Cycles
A cycle in a graph is a path that starts and ends at the same vertex and does not use any edge more than once. There are many cycles in this graph. The following are examples:
Two possible efficient network designs are shown below. Does either of the networks have any cycles?
An efficient network is a graph with just enough edges so that there is some path between any two pairs of vertices, but such that no edge could be removed and keep all vertices connected.
What does the existence of cycles tell you about the efficiency of a network?
If a cycle still exists, there is at least one superfluous or unnecessary edge.
Describe how a cycle is similar to an Euler circuit.
A cycle and an Euler circuit are almost exactly the same. The distinction is that a cycle does not have to include all edges, while the Euler circuits do.
Minimal Spanning Trees
A graph whose edges are given numerical values is called a weighted graph. Keeping all the vertices connected by a path resulting in a minimum total weight is called finding a minimal spanning tree. The word spanning means that each vertex remains connected to the graph, and the word tree indicates that there are no cycles.
The following procedure, known as Kruskal's Algorithm, can be used to find a minimal spanning tree in a weighted graph.
Kruskal's Algorithm
Assume that you start with a table of the weights associated with each edge.
Step 1: Put all of the weights in a list from smallest to largest.
Step 2: Find the smallest weight in the list and include the associated edge and two vertices, as long as that does not create a cycle.
Step 3: Remove this weight from the list.
Step 4: Repeat Steps 2 and 3 until all vertices are connected.
Minimal Spanning Tree
A railroad system connecting five cities is being planned. The goal is to build this system using the least amount of money, while ensuring that each city can be reached by any other city in the system. Based on the distance and terrain, the following chart gives estimates for the cost, in hundreds of thousands of dollars, to build a railroad between any two cities.
How can this situation be modeled with graphs?
Cities can be represented with vertices and possible railroad connections with edges. The cost for each segment of railroad needs to be noted on the graph next to each edge.
[CC BY-NC-SA 4.0] UNLESS OTHERWISE NOTED | IMAGES: LICENSED AND USED ACCORDING TO TERMS OF SUBSCRIPTION - INTENDED ONLY FOR USE WITHIN LESSON.