15-251Great Theoretical Ideas in Computer ScienceTest on MondayUpcoming EventsElection Day Review Session on Saturday (5 pm, Wean 5409)GraphsLecture 18, October 23, 2008A tree is a connected graph with no cyclesWhat’s a tree?TreeNot aTreeNot a TreeTreeHow Many n-Node Trees?1:2:3:4:5: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…)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. Prove that at a shy party with n people (n >= 2), at least two people have shaken hands with only one other person.The Shy People PartyThe Shy People PartyNotationIn this lecture:n will denote the number of nodes in a graphe will denote the number of edges in a graphTheorem: Let G be a graph with n nodes and e edgesThe following are equivalent:1. G is a tree (connected, acyclic)3. G is connected and n = e + 1 4. G is acyclic and n = e + 15. G is acyclic and if any two non-adjacent points are joined by a line, the resulting graph has exactly one cycle2. Every two nodes of G are joined by a unique pathTo 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 pathProof: (by contradiction)Assume G is a tree that has two nodes connected by two different paths:Then there exists a cycle!2 => 3 2. Every two nodes of G are joined by a unique pathProof: (by induction)Assume true for every graph with < n nodes3. G is connected and n = e + 1 Let G have n nodes and let x and y be adjacentLet n1,e1 be number of nodes and edges in G1Then n = n1 + n2 = e1 + e2 + 2 = e + 1 xyG1G2 3 => 4 Proof: (by contradiction)Assume G is connected with n = e + 1, and G has a cycle containing k nodes3. G is connected and n = e + 1 4. G is acyclic and n = e + 1k nodesNote that the cycle has k nodes and k edgesStart adding nodes and edges until you cover the whole graphNumber of edges in the graph will be at least nCorollary: 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 2Then the total number of edges in the tree is at least (2n-1)/2 = n - 1/2 > n - 1In any graph, sum of the degrees = 2eHow many labeled trees are there with three nodes?1 2 31 3 22 1 3How many labeled trees are there with four nodes?abcdHow many labeled trees are there with five nodes?5 labelings5 x x435!/ 2125 labeled treeslabelings labelingsHow many labeled trees are there with n nodes?16 labeled trees with 4 nodes3 labeled trees with 3 nodes125 labeled trees with 5 nodesnn-2 labeled trees with n nodesThe number of labeled trees on n nodes is nn-2Cayley’s FormulaThe proof will use the correspondence principleEach labeled tree on n nodescorresponds toA sequence in {1,2,…,n}n-2 (that is, n-2 numbers, each in the range [1..n])How to make a sequence from a tree?Example:51237486Loop through i from 1 to n-2Let L be the degree-1 node with the lowest labelDefine the ith element of the sequence as the label of the node adjacent to LDelete the node L from the tree1 3 3 4 4 4How to reconstruct the unique tree from a sequence S:Loop until S is emptyLet i = smallest # in I but not in SLet s = first label in sequence S Add edge {i, s} to the tree Delete i from I Delete s from SLet I = {1, 2, 3, …, n} Add edge {a,b}, where I = {a,b}521367481 3 3 4 4 4Spanning TreesA spanning tree of a graph G is a tree that touches every node of G and uses only edges from GEvery connected graph has a spanning treeA graph is planar if it can be drawn in the plane without crossing edgesExamples of Planar Graphs=http://www.planarity.netFacesA planar graph splits the plane into disjoint faces4 facesEuler’s FormulaIf G is a connected planar graph with n vertices, e edges and f faces, then n – e + f = 2Rather than using induction, we’ll use the important notion of the dual graphDual = put a node in every face, and an edge between every adjacent faceLet G* be the dual graph of GLet T be a spanning tree of GLet 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 + 1f = eT* + 1n + f = eT + eT* + 2= e + 2Corollary: Let G be a simple planar graph with n > 2 vertices. Then:1. G has a vertex of degree at most 52. G has at most 3n – 6 edgesProof of 1:Then e ! 3nIn any graph, (sum of degrees) = 2eFurthermore, since G is simple, 3f " 2eAssume all vertices have degree ! 6So 3n + 3f " 3e => 3(n-e+f) " 0, contradiction.A coloring of a graph is an assignment of a color to each vertex such that no neighboring vertices have the same colorGraph ColoringGraph ColoringArises surprisingly often in CSRegister allocation: assign temporary variables to registers for scheduling instructions. Variables that interfere, or are simultaneously active, cannot be assigned to the same registerInstructions Live variables ab = a+2 a,bc = b*b a,cb = c+1 a,breturn a*bab cTheorem: Every planar graph can be 6-coloredProof Sketch (by induction):Assume every planar graph with less than n vertices can be 6-coloredAssume G has n verticesSince G is planar, it has some node v with degree at most 5Remove v and color by Induction HypothesisNot too difficult to give an inductive proof of 5-colorability, using same fact that some vertex has degree " 54-color theorem remains challenging!Here’s What You Need to Know…Trees• Counting Trees• Different Characterizations• Cayley’s formulaPlanar Graphs• Definition• Euler’s Theorem• Coloring Planar
View Full Document