10 22 2009 15 251 Great Theoretical Ideas in Computer Science What s a tree Graphs I Lecture 18 October 22 2009 Tree A tree is a connected graph with no cycles Not a tree Not a tree 1 10 22 2009 Tree How Many n Node Trees 1 2 3 4 5 Theorem Let G be a graph with n nodes and e edges Notation In this lecture n will denote the number of nodes in a graph e will denote the number of edges in a graph The following are equivalent 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path 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 nodes are joined by an edge the resulting graph has exactly one cycle 1 2 1 G is a tree connected acyclic 2 Every two nodes of G are joined by a unique path Proof by contradiction To prove this it suffices to show 1 2 3 4 5 1 Assume G is a tree that has two nodes connected by two different paths Then there exists a cycle 2 10 22 2009 2 3 2 Every two nodes of G are joined by a unique path 3 4 3 G is connected and n e 1 Proof by contradiction Proof by induction Assume true for every graph with n nodes 3 G is connected and n e 1 4 G is acyclic and n e 1 Assume G is connected with n e 1 and G has a cycle containing k nodes Let G have n nodes and let x and y be adjacent k nodes G1 x y G2 Note that the cycle has k nodes and k edges Let n1 e1 be number of nodes and edges in G1 Start adding nodes and edges until you cover the whole graph Then n n1 n2 e1 e2 2 e 1 Number of edges in the graph will be at least n Corollary Every nontrivial tree has at least two endpoints points of degree 1 How many labeled trees are there with three nodes Proof by contradiction 1 2 3 In any graph sum of the degrees 2e 1 3 2 Then the total number of edges in the tree is at least 2n 1 2 n 1 2 n 1 2 1 3 Assume all but one of the points in the tree have degree at least 2 How many labeled trees are there with four nodes a c b d How many labeled trees are there with five nodes 5 labelings 5 x4 x3 labelings 5 2 labelings 125 labeled trees 3 10 22 2009 How many labeled trees are there with n nodes Cayley s Formula 3 labeled trees with 3 nodes The number of labeled trees on n nodes is nn 2 16 labeled trees with 4 nodes 125 labeled trees with 5 nodes nn 2 labeled trees with n nodes How to make a sequence from a tree Loop through i from 1 to n 2 The proof will use the correspondence principle Let L be the degree 1 node with the lowest label Each labeled tree on n nodes Define the ith element of the sequence as the label of the node adjacent to L corresponds to A sequence in 1 2 n n 2 that is n 2 numbers each in the range 1 n Delete the node L from the tree Example 5 1 8 4 3 2 6 7 1 3 3 4 4 4 Spanning Trees How to reconstruct the unique tree from a sequence S Let I 1 2 3 n A spanning tree of a graph G is a tree that touches every node of G and uses only edges from G 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 7 Every connected graph has a spanning tree 1 3 3 4 4 4 4 10 22 2009 Examples of Planar Graphs A graph is planar if it can be drawn in the plane without crossing edges Faces A planar graph splits the plane into disjoint faces http www planarity net 4 faces Euler s Formula Rather than using induction we ll use the important notion of the dual graph If G is a connected planar graph with n vertices e edges and f faces then n e f 2 Dual put a node in every face and an edge for each edge joining two adjacent faces 5 10 22 2009 Let G be the dual graph of G 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 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 3n e n eT 1 f eT 1 n f eT eT 2 e 2 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 Furthermore since G is simple 3f 2e So 3n 3f 3e 3 n e f 0 contradict 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 Theorem Every planar graph can be 6colored Proof Sketch by induction Assume every planar graph with less than n vertices can be 6 colored 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 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 6 10 22 2009 Adjacency Matrix Implementing Graphs Suppose 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 edge aij 0 if i j is not an edge Good for dense graphs Counting Paths Example A The number of paths of length k from node i to node j is the entry in position i j in the matrix Ak 0111 1011 1101 1110 0111 1011 1101 1110 3222 2322 2232 2223 0111 1011 1101 1110 Example Adjacency List Suppose we have a graph G with n vertices The adjacency list is the list that contains all the nodes that each node is adjacent to A2 1 3 2 4 1 2 3 …
View Full Document
Unlocking...