10/22/2009115-251Great Theoretical Ideas in Computer ScienceGraphs ILecture 18, October 22, 2009A tree is a connected graph with no cyclesWhat’s a tree?TreeNot a tree Not a tree10/22/20092TreeHow Many n-Node Trees?1:2:3:4:5:NotationIn 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 nodes are joined by an edge, the resulting graph has exactly one cycle2. Every two nodes of G are joined by a unique pathTo prove this, it suffices to show1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 5 ⇒ 11 ⇒ 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!10/22/200932 ⇒ 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,e1be number of nodes and edges in G1Then n = n1+ n2= e1+ e2+ 2 = e + 1 xyG1G23 ⇒ 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 (by contradiction):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 labelings10/22/20094How many labeled trees are there with n nodes?16 labeled trees with 4 nodes3 labeled trees with 3 nodes125 labeled trees with 5 nodesnn-2labeled 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:52136748Loop through i from 1 to n-2Let L be the degree-1 node with the lowest labelDefine the ithelement 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 SAdd edge {i, s} to the treeDelete i from IDelete 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 tree10/22/20095A 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 for each edge joining two adjacent faces10/22/20096Let 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 3n ≤ eIn 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, contradict.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 registerTheorem: 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!10/22/20097Implementing GraphsAdjacency MatrixSuppose we have a graph G with n vertices. The adjacency matrix is the n x n matrix A=[aij] with:aij= 1 if (i,j) is an edgeaij= 0 if (i,j) is not an edgeGood for dense graphs!ExampleA =0 1 1 11 0 1 11 1 0 11 1 1 0Counting PathsThe number of paths of length k from node i to node j is the entry in position (i,j) in the matrix AkA2=0 1 1 11 0 1 11 1 0 11 1 1 00 1 1 11 0 1 11 1 0 11 1 1 03 2 2 22 3 2 22 2 3 22 2 2 3=Adjacency ListSuppose we have a graph G with n vertices. The adjacency list is the list that contains all the nodes that each node is adjacent toGood for sparse graphs!Example12341: 2,32: 1,3,43: 1,2,44: 2,310/22/20098Here’s What You Need to Know…Trees• Counting Trees• Different CharacterizationsPlanar Graphs• Definition• Euler’s Theorem• Coloring Planar GraphsAdjacency Matrix and List• Definition• Useful for
View Full Document