15-251: Great Theoretical Ideas in Computer Science 15251 StaffNotes on Graph Theory II (draft!!) January 29, 20121 Minimum Spanning TreesGiven a graph G = (V, E), remember that a spanning tree is a tree that “spans” all thenodes. 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 Knon nvertices has nn−2spanning trees.Now suppose we are given a graph G = (V, E), where the edges have costs. I.e., each edgee ∈ E has a cost ce∈ R. For example, here is such a graph (which happens to have positiveinteger costs).122445558811127103And we want to find the spanning tree with the least cost, where the cost of the spanningtree T = (V, E0) isPe∈E0ce, the sum of its edge costs. Here is the minimum-cst spanningtree for the graph above.122445558811127103Very 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 ofthem in 15-451. Here is perhaps the simplest algorithm of them all.1.1 Kruskal’s AlgorithmThis “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), setF ← F ∪ {e}. OTOH, if adding e to F creates a cycle, just discard e.Return the subgraph T = (V, F ).1For example, you should check that running it on the example above gives the MST weclaimed. Note that if we start off with a connected graph, we would definitely end up witha spanning tree. (Why?) The claim is that this tree has the least cost possible, among allspanning 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 easilyextends to the general case.Proof: Suppose not. Suppose there is a spanning tree M = (V, E0), such that its costPe∈E0ce<Pe∈Fce. Then there must be some step in the algorithm where we pick an edgee into F , which did not belong to E0.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 dropthis edge, to get the new spanning tree N = (M ∪ {e}) \ {f}. If cf> ce, then N would havea 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 beenconsidered before e by Kruskal’s algorithm. But f does not belong to T , so the algorithmmust have discarded it. Why? This would only happen if adding f to the current edge setF would create a cycle.Hmm. All the edges in F at that time also belong to M (since all this happened beforewe reached e, and Kruskal agreed with the MST M until that time). And the edge f alsobelongs 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 ProblemConsider a setting where there are n cities, and a traveling salesman wants to find a tour ofthese cities. This is a permutation of the To be completed.2 Bipartite GraphsOne type of graph which arises often in applications is a bipartite graph. In such a graph, thevertex set V can be partitioned into two parts A and B = V \ A, and all edges go betweennodes 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—toemphasize this partition, we write a bipartite graph as a triple G = (A, B, E) instead of justa tuple G = (V, E). Also, we usually imagine the sets A as being on the left, and B on theright, and the edges going between the two sides—as in the following figure.22.1 Bipartite Graphs and No Odd CyclesTheorem 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− v1in G. As we traverse this cycle, we alternate between the sides: if v1is on the left,then all nodes vjfor j odd must be on the left, and vjfor even j on the right. Now there isan edge from vkto v1, so if v1is on the left vkis on the right, and hence the length of thecycle k is even.Conversely, suppose G has no cycles of odd length. (If G is not connected, do the followingon each connected component of G.) Pick any vertex v and perform a breadth-first searchfrom 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), thisforms a cycle of length 2` + 1, contradicting the fact that there are no odd cycles. So theonly 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 ColoringsWe often study colorings of graphs: these are maps that assign colors to the vertices of thegraph. We say a coloring is proper if no two vertices that are connected by an edge havethe same color. In other words, the coloring does not color the endpoints of any edge thesame.1A 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 nextsimplest case is already interesting —Theorem 2.2 A graph G is two-colorable if and only if it is bipartite.Proof: If G = (V, E) is bipartite, then V can be partitioned into two parts A and B = V \Asuch that all edges go between A and B. Hence we can color all vertices in A the same color,and those in B the other color.Conversely, suppose G is two-colorable. Let A be the vertices of color 1 and B be theremaining vertices. No edges can go between the nodes in A, or nodes in B, hence G =(A, B, E) is a bipartite graph. Combining Theorem 2.2 with Theorem 2.1 tells us that coloring any odd cycle requires atleast 3 colors.1The study of
View Full Document
Unlocking...