CSC263H1, Fall 2019 Problem Set 8 Sample Solutions
CSC263H1: Problem Set 8 Sample Solutions
Due Tuesday December 3 before 10pm
Note: solutions may be incomplete, and meant to be used as guidelines only. We encourage you to ask follow-up questions on the course forum or during office hours.
1. [12 marks] Bipartite Graphs: A graph G = (V, E) is bipartite if and only if it is possible to partition its vertices into two sets V1 and V2, so that all edges have one endpoint in each set. It is important to recognize when a graph is bipartite since there are many fast graph algorithms for this class of graphs.
(a) [5 marks] Show that a graph is bipartite if and only if it contains no odd cycle. (Note the if and only if means you need prove both ways)
Solution
Bipartite ⇒ no odd length cycle:
Assume G is bipartite, and for contradiction assume it has an odd length cycle. Let the cycle be {v1, v2}, {v2, v3}, · · · , {vm−1, vm}, {vm, v1}, where m is odd. Assume there is some partition V1, V2 like the one described above. Assume without loss of generality that v1 ∈ V1. Then it must be the case that v2 ∈ V2, v3 ∈ V1, · · · , vm ∈ V1 since m is odd. This contradicts the assumption that G is bipartite, since vm and v1 must be in different partitions, but they are both in V1. No odd length cycle ⇒ Bipartite:
Assume G(V,E) has no odd cycles. Let us also assume G is connected; if it is not, we can apply the argument herein to each component independently. Consider any spanning tree T of G. Choose one vertex (arbitrarily) of T as the ”root” r. (As a concrete example, select any vertex r and perform a depth first search of G starting from r to build T.) Every vertex v has a unique path to r on T. Color v white or black, depending on whether the path r v is even or odd in length, respectively. Because the colors alternate, the sets of white and black vertices form the two partitions, where edges of T have endpoints in opposite partitions. Assume (for contradiction) that two same-colored vertices, v1 and v2, are connected by a non-tree edge e ∈ E,e ̸∈ T. The paths r v1 and r v2 have lengths of equal parity, therefore the path v1 r v2 e v1 has odd length, which is a contradiction. Therefore, no two vertices of the same color are connected by an edge of G, and the sets of white and black vertices form the two partitions of a bipartite graph. QED.
(b) [2 marks] Does this correctness condition hold for a graph that is not connected? You can explain through an example
(c) [5 marks] Using a modified version of Depth-First search, design a function BIPARTITE(G) that, given a connected graph G in terms of its adjacency-list, returns TRUE if G is bipartite and FALSE otherwise. Show the run-time complexity of your algorithm as well.
Solution
Yes, it holds for disconnected graphs. Suppose some component of the graph has an odd length cycle (and thus is not bipartite). Additional non-connected vertices will not remove the odd length cycle, and so that component remains non-bipartite, so the graph is not bipartite.
Page 1/5
CSC263H1, Fall 2019 Problem Set 8 Sample Solutions
Solution
Note that if a graph is not connected, it suffices to show that each connected component is bipartite in order to show that the entire graph is bipartite, so we may assume the graph is connected.
We’ll let part[u] store the partition of each vertex u (either 1 or 2). When we start DFS on vertex s we set part[s] = 1, and whenever we set p[v] = u (recording the parent of v in the DFS tree) we’ll also set part[v] = 3 − part[u] (this alternates partitions so that if there is an edge between u and v then they are in different partitions).
If we expand an edge and find a grey or black vertex, check if part[u] = part[v] and if they are equal, output “not bipartite”
Page 2/5
CSC263H1, Fall 2019 Problem Set 8 Sample Solutions
2. [15 marks] Complete Graphs: A complete graph Kn is the undirected graph on n vertices in which every pair of vertices is joined by an edge.
(a) [5 marks] What is the running time of the breadth first search algorithm when the input graph is Kn?
(b) [5 marks] Modify BFS to obtain an algorithm which, given an undirected graph G with n vertices and m edges, determines whether it is connected in O(m + n) time, but whose running time for Kn is only Θ(n).
Solution
Θ(n + m). Every vertex is expanded, and every edge is inspected.
Solution
We slightly change BFS by using a counter-variable white vertices. We initially set this variable to n, and in the two places in the algorithm where a vertex is changed from white to gray we change the line
color[v] <- gray
to the following code:
color[v] <- gray
white_vertices <- white_vertices - 1
if white_vertices = 0 then return ‘‘connected’’
and we add the following line at the end of the algorithm:
return ‘‘disconnected’’
We call this new algorithm BFS-CONNECTED.
The running time of BFS-CONNECTED is still O(m + n), since the initialization and last step can be done in time O(n), and changing the update only increases the number of steps by a constant multiplicative factor. Since we did not change BFS itself the validity of our algorithm follows as described in class.
For Kn, BFS-CONNECTED terminates in O(n) steps, since from the very first vertex s we already find all other vertices (they are all colored gray) and the algorithm terminates (since white vertices is 0) without having examined any of the edges not incident to s. The initialization requires Ω(n) steps by itself, so we get a Θ(n) running time.
(c) [5 marks] Find a disconnected graph on n vertices for which the running time of the algorithm from (b) is Θ(n2), or explain why no such graph exists.
Solution
We take a complete graph on ⌊n/2⌋ vertices and a complete graph on ⌈n/2⌉ vertices to be the components of our disconnected graph on n vertices.
No matter in which component we start BFS-CONNECTED, the algorithm will have to examine every single edge of the component in which we start before the algorithm terminates by returning
“disconnected”. But each of the components has Θ((n/2)2) = Θ(n2) edges, and thus the running time is Θ(n2).
Page 3/5
CSC263H1, Fall 2019 Problem Set 8 Sample Solutions
3. [0 marks] Spanning:
This extra question is for your own edification. If you attempted it, we encourage you to
upload your solution, for our data, but it will not be marked.
Consider a weighted, undirected graph G = (V, E), where all edge weights are distinct:
(a) [0 marks] Define the term minimum spanning tree M of G, and prove that G has exactly one
minimum spanning tree. (Remember that no two edges have same weight)
Solution
A minimum spanning stree of a weighted graph G is connected acyclic subgraph of G with n − 1 vertices.
Suppose G has two distinct, MSTs, M1 and M2. Let S be the non-empty set of edges e such that e is in exactly one of M1 and M2. One of these edges has the smallest weight, call it e0 and without loss of generality it is in M1. M2 ∪ {e0} has some cycle C; C contains the edge e0, as well as some edge e1 ∈/ M1. (If all of C’s edges were in M1 then M1 would contain a cycle).
By our choice of e0 we know w(e0) < w(e1), and since both are in the cycle C we can remove e1 from M2 and add e0 to M2 to get an MST of lower weight. This contradicts the original assumptions about M2.
(b) [0 marks] Do Prim’s and Kruskal’s algorithms still work if the edge weights are allowed to be negative?
Solution
Yes. The algorithms have no special behaviour around negative weight edges. Alternatively, we could modify the graph as follows:
Suppose G has some edge weights that are negative, in particular edge e has the lowest weight of we < 0. Add |we + 1| to all edge weights. Now all edges have positive weights. Run Kruskal’s or
Prim’s algorithm as usual to find an MST. The resulting MST will be exactly equivalent (same edges, different weights) to an MST of G before the modification.
(c) [0 marks] Suppose that we have already computed a minimum-weight spanning tree M in a weighted, undirected graph G. Now suppose we want to either
(i) increase the weight of one of the edges in M or
Solution
Let (u,v) be the edge in M whose weight increased. Using DFS or BFS, mark all the nodes reachable from u in M without passing through v and call this set A. Similarly, mark all the nodes reachable from v without going through u and call this set B.
Check each edge that isn’t in M for the lightest edge e that connects a node in A with a node in B. If the weight of e is less than the new weight of (u,v) replace (u,v) with e in M.
(ii) decrease the weight of one of the edges of G not in M.
Solution
Let (u, v) be the edge whose weight decreased. Run BFS in M to find the shortest simple path from u to v, and find the edge e of maximal weight along that path. If the weight of e if greater
Page 4/5
CSC263H1, Fall 2019 Problem Set 8 Sample Solutions
than the new weight of (u,v) then replace e with (u,v) in M.
In either case M may no longer be of minimum weight, and we may have to compute a new minimum- weight spanning tree. Describe linear-time (O(n + m)) algorithms for each of these two problems. For (i), assume that the edges not in M are sorted by weight. Describe your algorithms in high-level terms, no pseudocode.
Page 5/5