Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42COMPSCI 102Introduction to Discrete MathematicsGraphsLecture 19 (November 2, 2009)A tree is a connected graph with no cyclesWhat’s a tree?TreeNot TreeNot TreeTreeHow 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 points are joined by adding a new edge, 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 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!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 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 edgesStarting from cycle, add other 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 labelings54335422125 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:52136748Loop 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 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}Spanning 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=FacesA 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 (by contradiction):Then e ≥ 3nIn any graph, (sum of degrees) = 2eFurthermore, since G is simple, 3f ≤ 2eAssume all vertices have degree ≥ 6So 3n + 3f ≤ 3e, 3n + 3f = 3e + 6, and 3e + 6 ≤ 3eA 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!Implementing 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,3Here’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
Unlocking...