This week we will be finishing up the graph theory material with a discussion of trees and spanning trees. A tree is just a connected graph which contains no circuits. We will be concerned with finding subgraphs of graphs which contain all the original vertices and are trees. These are called spanning trees. Kruskal's algorithm gives us a way to find a spanning tree of minimal weight in a weighted graph. This algorithm should feel familiar to you; it is very similar to the Side Sorted Algorithm, except now our goal will be to end up with a spanning tree rather than a Hamiltonian circuit.
Exam 1 will be in class on Monday, February 6. Make sure to bring your graded worksheets to class with you on Monday to turn in. I have posted an exam review on the right hand side of the blog and below. Please print this out and bring it to class with you on Wednesday February 1. (Don't forget you must be logged in to your MWSU email account to access this.)
Graph Theory Exam Review
Challenge Problem: A connected graph G has 18 vertices. How many edges does a spanning tree of G have? How many vertices does a spanning tree of G have? What can one say about the number of edges G has?
I think trees are a little confusing because you don't need to end up where you started but you are still trying to basically use the smallest weights to form a path. I think memorizing the steps to each path is the only way to get through.
ReplyDeleteYour goal with a minimal spanning tree is to make a connected subgraph that contains all the original vertices of the graph and has the minimum possible total weight. You don't want to think of it in terms of a path, but as a subgraph (which contains paths between any pair of vertices).
ReplyDeleteYes! :)
ReplyDeleteGood! :)
ReplyDelete