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.
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?
No comments:
Post a Comment