Unformatted text preview:

CS/Math 240: Introduction to Discrete Mathematics 4/12/2011Lecture 20 : TreesInstructor: Dieter van Melkebeek Scribe: Dalibor Zelen´yDRAFTLast time we discussed graphs. Today we continue this discussion, and focus on graphs of aspecial kind, trees. Afterwards, we start discussing applications of graphs in computer science.We talk about graph coloring today, and we’ll mention finite state machines, finite automata, andregular expressions in the next lecture.20.1 TreesBefore we describe trees, we revisit the notion of a path.We need the concept of a simple path. A simple path is just like any other path, except everyedge appears on it at most once, and the only vertex that can be visited twice is the start vertex,but only if the second visit is at the very end of the path. If the start vertex is the same as the endvertex, the path is called a simple cycle.Example 20.1: Consider the graph in Figure 20.1. We show some simple paths as well as somepaths that are not simple. ⊠0 1 23 4 5(a) A simple path from 0 to 3.0 1 23 4 5(b) A simple cycle that starts andends at 1.0 1 23 4 5(c) A path from 0 to 1 that is not sim-ple. The last vertex is a previously-visited vertex, but not the start ver-tex.0 1 23 4 5(d) A path from 0 to 3 that is notsimple. The vertex 1 appears twice.The edge taken after the first visit to1 is (1, 2).Figure 20.1: Examples illustrating the definition of a simple path. The arrows give the directioneach edge is traversed in.In a simple graph, there is at most one edge between any one pair of vertices. Thus, we canlist the vertices on the path instead of listing the edges. If the path goes from vertex u to vertex vin one step, there is a unique edge this path can follow to achieve that. Hence, we can recover thesequence of edges from the sequence of vertices visited on the path.1Lecture 20: Trees 20.1. TreesFor example, we could describe the path in Figure 20.1a using the sequence 0, 1, 2, 5, 4, 3 insteadof the sequence {0, 1}, {1, 2}, {2, 5}, {5, 4}, {4, 3}.And now we are ready to define what a tree is.Definition 20.1. A tree is a connected graph without simple cycles.We show three graphs in Figure 20.2. Only the first graph is a tree. The remaining two arenot. One is not connected and one is not acyclic.(a) A tree (b) Not a tree because thegraph has two connected com-p onents.(c) Not a tree because there isa simple cycle in this graph.The edges on that cycles arehighlighted using thick bluelines.Figure 20.2: Examples illustrating the definition of a tree.Now the graph in Figure 20.2a doesn’t exactly look like a tree. So let’s redraw it to makeit look more like a tree. Pick an arbitrary node (in this case we pick the only one of degree 4),and consider it the root of the tree. Draw its neighbors above it, then draw the neighbors of theneighbors (except for the root which has already been drawn) one more level above, and keep goinguntil the entire graph is drawn. We show this process in Figure 20.3, with the graph taking a treeform in Figure 20.3b.Every vertex of degree 1 in a tree is called a leaf. For example, the leaves in Figure 20.3b arevertices 0, 4, 6, 8, and 9.We declared the vertex 3 the root of the tree in Figure 20.3b, but that is only a product of howwe drew the tree. To give the r oot some significance, we make all the edges directed, so that theyall point away from the root. The resulting tree, called a rooted tree, is shown in Figure 20.3c. Nowthe concept of a root makes sense. It is the only vertex with in-degree zero. All the other verticeshave in-degree 1.012345 6789(a) A tree01234 5678 9(b) Now it looks more like a tree.01234 5678 9(c) In a rooted tree, all edges p ointaway from the root.Figure 20.3: Pick node 3 as the root. Then draw all its neighbors i n the next level. One level above,draw the neighbors of the root’s neighbors. Keep going in this fashion until the entire picture isdrawn.2Lecture 20: Trees 20.1. Trees20.1.1 Properties of TressGiven their special structure, we can prove more facts about trees. In particular, we describe somerelationships between the vertex and edge sets of trees.Proposition 20.2. Let T = (V, E) be a tree. Then the following are true.(i) If |V | ≥ 2, T has at least two leaves.(ii) There is exactly one simple path between any two vertices.(iii) If V is nonempty, |V | = |E| + 1.We make some remarks about individual parts of Proposition 20.2, and then prove the individualparts.If there is just one vertex in the graph, we consider the graph a tree if there are no edges, andwe call the only vertex a leaf in that case. If there are at least two vertices, the characterization ofthe number of leaves from part (i) applies.Proof of part (i) of Proposition 20.2. Consider a simple path P of maximum length in the tree T .Say P starts at u, ends in v, and the vertices on the path are u = v0, v1, . . . , vr−1, vr= v. We claimthat u and v have degree 1, which means they are leaves.Suppose u does not have degree 1. Then there is another edge besides {u, u1} that’s incidenton u, say {w, u}. This edge does not appear on the path P because P is si mple. There are twocases to consider, and each of them leads to a contradiction.Case 1: w does not appear on the path P . Then the path w, u, v1, . . . , vr, v is a simple pathlonger than P , which is a contradiction because P is the longest simple path in T .Case 2: w appears on the path P , say w = vi. Then the path w = vi, vi+1, . . . , vr, viis a simplecycle in T . But since T doesn’t contain any simple cycles, this is a contradiction.Part (ii) of Proposition 20.2 actually gives us an equivalent definition of a tree. That is, aconnected graph with exactly one simple path between any two vertices is a tree. We leave theproof of this fact as an exercise to the reader.Because T is connected, there is a path between any two vertices in T . We first show that thisimplies the existence of a simple path between any two vertices in T . For example, consider thepath in Figure 20.1d. We could turn it into a simple path by omitting the cycle 1, 2, 5, 4, 1, andjust going to 3 the moment we reach 1 for the first time. In fact, this strategy works in general. Ifa cycle is part of a path from u to v, the part of the path without the cycle is a shorter path fromu to v. After removing some number of cycles in this fashion, we end with a simple path.Lemma 20.3. Let G = (V, E) be a graph. If there is a path from vertex u to …


View Full Document

UW-Madison CS 240 - Trees

Download Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Trees 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?