15 251 Great Theoretical Ideas in Computer Science Graphs II Lecture 19 October 28 2008 Recap 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 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 Cayley s Formula Cayley s Formula The number of labeled trees on n nodes is nn 2 A graph is planar if A graph is planar if it can be drawn in the plane without crossing edges Euler s Formula Euler s Formula If G is a connected planar graph with n vertices e edges and f faces then n e f 2 Graph Coloring 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 Spanning Trees Spanning Trees A spanning tree of a graph G is a tree that touches every node of G and uses only edges from G Spanning Trees A spanning tree of a graph G is a tree that touches every node of G and uses only edges from G Every connected graph has a spanning tree Implementing Graphs Adjacency Matrix Adjacency Matrix Suppose we have a graph G with n vertices The adjacency matrix is the n x n matrix A aij with Adjacency Matrix 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 Adjacency Matrix 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 Example Example A 0111 1011 1101 1110 Counting Paths The number of paths of length k from node i to node j is the entry in position i j in the matrix Ak Counting Paths The number of paths of length k from node i to node j is the entry in position i j in the matrix Ak Counting Paths The number of paths of length k from node i to node j is the entry in position i j in the matrix Ak A2 Counting Paths The number of paths of length k from node i to node j is the entry in position i j in the matrix Ak A2 0111 1011 1101 1110 0111 1011 1101 1110 Counting Paths The number of paths of length k from node i to node j is the entry in position i j in the matrix Ak A2 0111 1011 1101 1110 3222 2322 2232 2223 0111 1011 1101 1110 Adjacency List 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 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 Good for sparse graphs Example 1 3 2 4 Example 1 3 2 4 1 2 3 2 1 3 4 3 1 2 4 4 2 3 Graphical Muzak Can you hear the shape of a graph http www math ucsd edu fan hear Finding Optimal Trees Finding Optimal Trees Trees have many nice properties uniqueness of paths no cycles etc Finding Optimal Trees Trees have many nice properties uniqueness of paths no cycles etc We may want to compute the best tree approximation to a graph Finding Optimal Trees Trees have many nice properties uniqueness of paths no cycles etc We may want to compute the best tree approximation to a graph If all we care about is communication then a tree may be enough We want a tree with smallest communication link costs Finding Optimal Trees Problem Find a minimum spanning tree that is a tree that has a node for every node in the graph such that the sum of the edge weights is minimum Tree Approximations 7 8 4 5 9 7 8 6 11 9 Tree Approximations 7 8 4 5 9 7 8 6 11 9 Kruskal s Algorithm A simple algorithm for finding a minimum spanning tree Finding an MST Kruskal s Algorithm Finding an MST Kruskal s Algorithm Create a forest where each node is a separate tree Finding an MST Kruskal s Algorithm Create a forest where each node is a separate tree Make a sorted list of edges S Finding an MST Kruskal s Algorithm Create a forest where each node is a separate tree Make a sorted list of edges S While S is non empty Finding an MST Kruskal s Algorithm Create a forest where each node is a separate tree Make a sorted list of edges S While S is non empty Remove an edge with minimal weight Finding an MST Kruskal s Algorithm Create a forest where each node is a separate tree Make a sorted list of edges S While S is non empty Remove an edge with minimal weight If it connects two different trees add the edge Otherwise discard it Applying the Algorithm 7 4 1 5 9 9 10 8 7 3 Applying the Algorithm 7 4 1 5 9 9 10 8 7 3 Applying the Algorithm 7 4 1 5 9 9 10 8 7 3 Applying the Algorithm 7 4 1 5 9 9 10 8 7 3 Applying the Algorithm 7 4 1 5 9 9 10 8 7 3 Applying the Algorithm 7 4 1 5 9 9 10 8 7 3 Applying the Algorithm 7 4 1 5 9 9 10 8 7 3 Analyzing the Algorithm Analyzing the Algorithm The algorithm outputs a spanning tree T Analyzing the Algorithm The algorithm outputs a spanning tree T Suppose that it s not minimal For simplicity assume all edge weights in graph are distinct Analyzing the Algorithm The algorithm outputs a spanning tree T Suppose that it s not minimal For simplicity assume all edge weights in graph are distinct Let M be a minimum spanning tree Analyzing the Algorithm The algorithm outputs a spanning tree T Suppose that it s not minimal For simplicity assume all edge weights in graph are distinct Let M be a minimum spanning tree Let e be the first edge chosen by the algorithm that is not in M Analyzing the Algorithm The algorithm outputs a spanning tree T Suppose that it s not minimal For simplicity assume all edge weights in graph are distinct Let M be a minimum spanning tree Let e be the first edge chosen by the algorithm that is not in M If we add e to M it creates a cycle Since this cycle isn t fully contained …
View Full Document
Unlocking...