15 251 Great Theoretical Ideas in Computer Science Notes on Graph Theory II draft 1 15251 Staff January 29 2012 Minimum Spanning Trees Given a graph G V E remember that a spanning tree is a tree that spans all the nodes In other words it is a tree connected acyclic graph on all the nodes V Evert connected graph has a spanning tree Some graphs may have several spanning trees In fact you already saw Cayley s formula which says that the complete graph Kn on n vertices has nn 2 spanning trees Now suppose we are given a graph G V E where the edges have costs I e each edge e E has a cost ce R For example here is such a graph which happens to have positive integer costs 2 1 10 5 7 8 3 2 5 4 11 12 5 8 4 And we want to find Pthe spanning tree with the least cost where the cost of the spanning tree T V E 0 is e E 0 ce the sum of its edge costs Here is the minimum cst spanning tree for the graph above 2 1 10 5 7 8 2 5 4 8 11 12 3 5 4 Very often the minimum cost spanning tree gets shortened to minimum spanning tree or MST There are many algorithms to solve this problem you will probably see some of them in 15 451 Here is perhaps the simplest algorithm of them all 1 1 Kruskal s Algorithm This greedy algorithm for MST is due to Joseph Kruskal Start off with an edge set F Create a list L of the edges in non decreasing order of weight While L is not empty pick a least cost edge e from L If adding e to the set F creates no cycles i e it connects two components set F F e OTOH if adding e to F creates a cycle just discard e Return the subgraph T V F 1 For example you should check that running it on the example above gives the MST we claimed Note that if we start off with a connected graph we would definitely end up with a spanning tree Why The claim is that this tree has the least cost possible among all spanning trees Theorem 1 1 Kruskal s algorithm returns a spanning tree T V F of minimum cost We give the proof for the special case where all the edge costs are different The proof easily extends to the general case Proof Suppose not Suppose there is a spanning tree M V E 0 such that its cost P P e E 0 ce e F ce Then there must be some step in the algorithm where we pick an edge e into F which did not belong to E 0 Now consider adding e to M Since M was a tree adding e to it creates a single cycle C Since T was acyclic there must be some edge f C that does not belong to T So drop this edge to get the new spanning tree N M e f If cf ce then N would have a lower cost than M and we would get a contradiction So cf ce They cannot be equal since we assumed distinct costs So f must have been considered before e by Kruskal s algorithm But f does not belong to T so the algorithm must have discarded it Why This would only happen if adding f to the current edge set F would create a cycle Hmm All the edges in F at that time also belong to M since all this happened before we reached e and Kruskal agreed with the MST M until that time And the edge f also belongs to M So M contains a cycle Which is a contradiction Exercise Extend the proof to the case where different edges may have the same costs Hint where was the only point you used the assumption of distinct costs 1 2 An Application Traveling Salesman Problem Consider a setting where there are n cities and a traveling salesman wants to find a tour of these cities This is a permutation of the To be completed 2 Bipartite Graphs One type of graph which arises often in applications is a bipartite graph In such a graph the vertex set V can be partitioned into two parts A and B V A and all edges go between nodes in A and those in B I e E A B So to show a graph is bipartite you need to exhibit this partition of the vertex set to emphasize this partition we write a bipartite graph as a triple G A B E instead of just a tuple G V E Also we usually imagine the sets A as being on the left and B on the right and the edges going between the two sides as in the following figure 2 2 1 Bipartite Graphs and No Odd Cycles Theorem 2 1 A graph is bipartite if and only if it contains no cycles of odd length Proof Suppose G A B E is bipartite then consider any cycle C v1 v2 v3 vk v1 in G As we traverse this cycle we alternate between the sides if v1 is on the left then all nodes vj for j odd must be on the left and vj for even j on the right Now there is an edge from vk to v1 so if v1 is on the left vk is on the right and hence the length of the cycle k is even Conversely suppose G has no cycles of odd length If G is not connected do the following on each connected component of G Pick any vertex v and perform a breadth first search from v Recall that in BFS all edges either go between adjacent levels or within a level But if there is some edge between two vertices on level where the root is at level 0 this forms a cycle of length 2 1 contradicting the fact that there are no odd cycles So the only edges must go between levels Define A to be the even numbered levels of this BFS and B to be the odd numbered levels then G A B E is a bipartite graph Since a tree does not have any cycles at all and hence no odd cycles a tree is bipartite 2 2 Bipartite Graphs and Graph Colorings We often study colorings of graphs these are maps that assign colors to the vertices of the graph We say a coloring is proper if no two vertices that are connected by an edge have the same color In other words the coloring does not color the endpoints of any edge the same 1 A graph G is k colorable if there exists a proper coloring for G that uses at most k colors Note that a graph is 1 colorable if and only if it does not have any edges at all The next simplest case is already interesting …
View Full Document
Unlocking...