View Full Document

# General Trees and Spanning Trees

View Full Document
View Full Document

3 views

Unformatted text preview:

General Trees and Spanning Trees Briefly Discrete Math Section 13 4 I General Trees We ve already talked in detail about binary trees We take a moment here to analyze general trees Note all trees all graphs Definition A graph is circuit free iff it has no nontrivial circuit Definition A graph is called a tree iff it is 1 circuit free 2 connected Special Trees trivial tree a single vertex empty tree no vertex Definition A graph is called a forest iff it is circuit free Examples Note The trees we ve studied and the most commonly used trees can be called rooted trees Specifically they are binary trees II Trees Within Graphs Question Consider the college campus graph see a modified form to the right we worked with when studying paths and walks Suppose each edge represents a sidewalk Do we need all of the paths to get from any building to any other building Question Is there a tree within the graph Question Why do we care Answer Efficiency We d like to minimize the total number of routes while still maintaining connectivity Definition A spanning tree for a graph G is a subgraph of G that contains every vertex of a G and is a tree Example See above Theorem Any connected graph has a spanning tree Notice the use of language here A spanning tree logically says there must be one spanning tree It does not rule out the possibility that there is more than one spanning tree We d say exactly one in that case While some graphs will have exactly one spanning tree most will have many Scenario not as far fetched as you might think but yes maybe a little exaggerated Consider the campus graph again A giant blizzard suddenly hits the area and the campus is covered is five feet of snow Classes must go on The snow removal team needs to clear the pathways so we can get from any building to any other building There s no time to waste so we need to clear the least distance of sidewalks possible to accomplish this goal People may need to go out of their way to get somewhere but at least they

Unlocking...