Topics
Subgraphs, Trees and MSTs
0 of 0 exercises completed
The notion of a subgraph, and special types of graphs called trees. Kruskal's and Prim's algorithms for finding minimum spanning trees.
Want a deeper conceptual understanding? Try our interactive lesson!
Subgraphs
AHL AI 3.14
Taking an existing graph and erasing one or more vertex or edge produces a smaller graph called a subgraph.
Original Graph
Subgraph examples
Trees
AHL AI 3.14
A tree is a graph that is
connected
simple
has no cycles
Number of edges in a tree
AHL AI 3.14
A tree with n vertices always has exactly n−1 edges.
To see why this is true imagine starting with no edges (everything is disconnected), and adding edges 1 at a time.
The first edge we add connects 2 vertices, so our tree has 2 vertices and 1 edge
Then, we add an edge connecting one of these two vertices to one we have not connected to yet. This adds 1 new vertex to the tree, so now we have 3 vertices and 2 edges.
We keep going until we stop, and we have n vertices and n−1 edges.
We cannot have any more edges, because now that every vertex is connected, adding another edge would form a loop somewhere!
Minimum spanning trees
AHL AI 3.14
A minimum spanning tree is a tree with the smallest possible weight that connects every vertex in a graph. It is often given the abbreviation "MST".
Basically, the smallest sum of edges that keep everything connected. The total weight of the minimum spanning tree is then just the sum of the weights of the edges in the tree.
Below you can see a graph and its minimum spanning tree.
The total weight of the minimum spanning tree is 3+3+2+4+5=17.
Note that MSTs are not unique - some graphs have multiple MSTs with the same weight. For example, another MST for the graph above is:
Kruskal's Algorithm
AHL AI 3.16
Kruskal's Algorithm is a procedure for finding minimum spanning trees on a graph.
The algorithm works by selecting edges one at a time, starting with the smallest weight edge and working our way up. Any edge that would form a cycle (a loop of vertices) with the edges we've already selected gets skipped. We stop when every vertex is connected.
The following animation shows the process for one particular graph.
Note that there will often be ties for edge weights. This is the reason why minimum spanning trees are not unique, even though they all have the same total weight.. In IB questions, any valid MST will be accepted.
Prim's Algorithm
AHL AI 3.16
Prim's Algorithm is an algorithm for finding minimum spanning trees.
It works very similar to Kruskal's Algorithm, adding edges one at a time in order of smallest to largest weights, without forming cycles. The differences are that with Prim's algorithm:
We can start at any vertex, often specified in the question
we can only add edges that connect to the tree we've made so far.
Below is a side by side comparison of each step.
Prim's
Kruskal's
The difference is that at every step, all the vertices in Prim's algorithm are connected, while in Kruskal's they can be temporarily disconnected. They both produce trees of the same weight, and often will produce an identical tree.
Prim's Algorithm on an adjacency matrix
AHL AI 3.16
Prim's algorithm is ideal for finding the minimum spanning tree when we have the adjacency table of a graph, instead of the graph itself.
Consider this example:
Algorithm
1. Select a random starting vertex if it is not given.
Let's start at B.
2. Delete the row for that vertex (or cross it out).
3. Number the column of the chosen vertex.
The 1st vertex we chose was B, so we put a 1 above that column.
4. Find the lowest number in a column, and circle it.
For us this is the 9 in row E. If there was a tie, we would just pick randomly.
5. Repeat steps 2-4 until all rows are deleted.
We just selected row E, so we delete that row, and add a 2 in the column above it.
Now we have columns B and E, so we look for the smallest number in those columns. That number is 8, which connects to A. So now we delete row A, number column A with a 3, and continue.
The next smallest number in a valid column is the 2 in row D. So we delete that row, and number that column with a 4.
Now we have columns A, B, D and E. The smallest remaining edge weight in any of those rows is the 13 in row C. So we circle it, cross out that row, and add a 5 above the column for C.
Now that all the rows are crossed out, we read the tree by looking at the cells we have circled:
BE with weight 9
AE with weight 8
AC with weight 13
AD with weight 2
Nice work completing Subgraphs, Trees and MSTs, here's a quick recap of what we covered:
Skills covered
Exercises checked off
I'm Plex, here to help you understand this concept!