15 251 Graphs Lecture 18 October 23 2008 Great Theoretical Ideas in Computer Science What s a tree Upcoming Events Review Session on Saturday 5 pm Wean 5409 Test on Monday Election Day A tree is a connected graph with no cycles Tree Not a Tree Tree Not aTree How Many n Node Trees 1 The Shy People Party At the shy people party people enter one by one and as a person comes in s he shakes hand with only one person already at the party 2 3 4 Prove that at a shy party with n people n 2 at least two people have shaken hands with only one other person 5 The Shy People Party We ll pass around a piece of paper Draw a new 8 node tree and put your name next to it There are 23 of them Notation In this lecture n will denote the number of nodes in a graph e will denote the number of edges in a graph Theorem Let G be a graph with n nodes and e edges The following are equivalent 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path To prove this it suffices to show 1 2 3 4 5 1 1 2 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path Proof by contradiction Assume G is a tree that has two nodes connected by two different paths 3 G is connected and n e 1 4 G is acyclic and n e 1 5 G is acyclic and if any two non adjacent points are joined by a line the resulting graph has exactly one cycle Then there exists a cycle 2 3 2 Every two nodes of G are joined by a unique path 3 G is connected and n e 1 Proof by induction Assume true for every graph with n nodes Let G have n nodes and let x and y be adjacent G1 x y G2 Corollary Every nontrivial tree has at least two endpoints points of degree 1 Proof Assume all but one of the points in the tree have degree at least 2 In any graph sum of the degrees 2e Then the total number of edges in the tree is at least 2n 1 2 n 1 2 n 1 Let n1 e1 be number of nodes and edges in G1 Then n n1 n2 e1 e2 2 e 1 3 4 3 G is connected and n e 1 4 G is acyclic and n e 1 Proof by contradiction Assume G is connected with n e 1 and G has a cycle containing k nodes k nodes How many labeled trees are there with three nodes 1 2 3 1 3 2 2 1 3 Note that the cycle has k nodes and k edges Start adding nodes and edges until you cover the whole graph Number of edges in the graph will be at least n How many labeled trees are there with four nodes How many labeled trees are there with n nodes a c 3 labeled trees with 3 nodes b d 16 labeled trees with 4 nodes 125 labeled trees with 5 nodes nn 2 labeled trees with n nodes How many labeled trees are there with five nodes Cayley s Formula The number of labeled trees on n nodes is nn 2 5 labelings 5 x 4 x3 labelings 5 2 labelings 125 labeled trees The proof will use the correspondence principle How to reconstruct the unique tree from a sequence S Let I 1 2 3 n Each labeled tree on n nodes corresponds to A sequence in 1 2 n n 2 that is n 2 numbers each in the range 1 n Loop until S is empty Let i smallest in I but not in S Let s first label in sequence S Add edge i s to the tree Delete i from I 5 Delete s from S 3 1 Add edge a b where I a b 2 8 4 6 1 3 3 4 4 4 How to make a sequence from a tree Loop through i from 1 to n 2 Let L be the degree 1 node with the lowest label Define the ith element of the sequence as the label of the node adjacent to L Spanning Trees A spanning tree of a graph G is a tree that touches every node of G and uses only edges from G Delete the node L from the tree Example 5 1 8 4 3 2 6 1 3 3 4 4 4 7 Every connected graph has a spanning tree 7 A graph is planar if it can be drawn in the plane without crossing edges http www planarity net Examples of Planar Graphs Faces A planar graph splits the plane into disjoint faces 4 faces Let G be the dual graph of G Euler s Formula If G is a connected planar graph with n vertices e edges and f faces then n e f 2 Let T be a spanning tree of G Let T be the graph where there is an edge in dual graph for each edge in G T Then T is a spanning tree for G n eT 1 f eT 1 Rather than using induction we ll use the important notion of the dual graph n f eT eT 2 e 2 Corollary Let G be a simple planar graph with n 2 vertices Then 1 G has a vertex of degree at most 5 2 G has at most 3n 6 edges Proof of 1 In any graph sum of degrees 2e Assume all vertices have degree 6 Then e 3n Dual put a node in every face and an edge between every adjacent face Furthermore since G is simple 3f 2e So 3n 3f 3e 3 n e f 0 contradiction Graph Coloring A coloring of a graph is an assignment of a color to each vertex such that no neighboring vertices have the same color Instructions Live variables a b a 2 a b c b b a c b c 1 a b return a b a b Graph Coloring Arises surprisingly often in CS Register allocation assign temporary variables to registers for scheduling instructions Variables that interfere or are simultaneously active cannot be assigned to the same register c Theorem Every planar graph can be 6colored Proof Sketch by induction Assume every planar graph with less than n vertices can be 6 colored Assume G has n vertices Since G is planar it has some node v with degree at most 5 Remove v and color by Induction Hypothesis Not too difficult to give an inductive proof of 5 colorability using same fact that some vertex has degree 5 4 color theorem remains challenging Trees Counting Trees Different Characterizations Cayley s formula Planar Graphs Definition Euler s Theorem Coloring Planar Graphs Here s What You Need to Know
View Full Document
Unlocking...