10 30 2009 15 251 Graphs II Lecture 19 October 27 2009 Great Theoretical Ideas in Computer Science Theorem Let G be a graph with n nodes and e edges The following are equivalent 1 G is a tree connected acyclic Recap 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 The number of labeled trees on n nodes is nn 2 A graph is planar if it can be drawn in the plane without crossing edges 1 10 30 2009 Planar Graphs http www planarity net 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 Euler s Formula If G is a connected planar graph with n vertices e edges and f faces then n e f 2 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 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 2 10 30 2009 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 2 1 3 4 3 1 2 4 4 2 3 Good for sparse graphs Graphical Muzak Can you hear the shape of a graph http www math ucsd edu fan hear 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 3 10 30 2009 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 9 11 Kruskal s Algorithm Finding an MST Kruskal s Algorithm Create a forest where each node is a separate tree A simple algorithm for finding a minimum spanning 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 Analyzing the Algorithm The algorithm outputs a spanning tree T 7 4 1 5 9 9 10 Let M be a minimum spanning tree 8 7 3 Suppose that it s not minimal For simplicity assume all edge weights in graph are distinct 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 in T it has an edge f not in T N M e f is another spanning tree 4 10 30 2009 Analyzing the Algorithm N M e f is another spanning tree Claim e f and therefore N M Suppose not e f Then f would have been visited before e by the algorithm but not added because adding it would have formed a cycle Greed is Good In this case The greedy algorithm by adding the least costly edges in each stage succeeds in finding an MST But in math and life if pushed too far the greedy approach can lead to bad results But all of these cycle edges are also edges of M since e was the first edge not in M This contradicts the assumption M is a tree TSP from Trees TSP Traveling Salesman Problem Given a number of cities and the costs of traveling from any city to any other city what is the cheapest round trip route that visits each city exactly once and then returns to the starting city We can use an MST to derive a TSP tour that is no more expensive than twice the optimal tour Idea walk around the MST and take shortcuts if a node has already been visited We assume that all pairs of nodes are connected and edge weights satisfy the triangle inequality d x y d x z d z y Tours from Trees Bipartite Graph Shortcuts only decrease the cost so Cost Greedy Tour 2 Cost MST 2 Cost Optimal Tour This is a 2 competitive algorithm A graph is bipartite if the nodes can be partitioned into two sets V1 and V2 such that all edges go only between V1 and V2 no edges go from V1 to V1 or from V2 to V2 5 10 30 2009 Dancing Partners Dancing Partners A group of 100 boys and girls attend a dance Every boy knows 5 girls and every girl knows 5 boys Can they be matched into dance partners so that each pair knows each other Perfect Matchings A matching is a set of edges no two of which share a vertex The matching is perfect if it includes every vertex Theorem If every node in a bipartite graph has the same degree d 1 then the graph has a perfect matching Note if degrees are the same then A B where A is the set of nodes on the left and B is the set of nodes on the right A Matter of Degree Claim If degrees are the same then A B Proof If there are m boys there are md edges If there are n girls there are nd edges We ll now prove a stronger result The Marriage Theorem The Marriage Theorem Theorem A bipartite graph has a perfect matching if and only if A B n and for all k 1 n for any subset of k nodes of A there are at least k nodes of B that are connected to at least one of them For any subset of say k nodes of A there are at least k nodes of B that are connected to at least one of them The condition fails for this graph 6 10 30 2009 The Feeling is Mutual At least k At most n k k n k Proof of Marriage Theorem Call a bipartite graph matchable if it has the same number of nodes on left and right and any k nodes on the left are connected to …
View Full Document
Unlocking...