22.1-6
We start at the position (1, 1) of the adjacency matrix and move to neighboring positions based
on the value at the current position. If the value of the current position (i, j) is 1, there’s an edge
from i to j, so that i cannot be the universal sink and we move to (i + 1, j). Otherwise, j cannot be
the universal sink and we move to (i, j + 1). We stop once i or j is |V|. Notice that the only possible universal sink is node i at the stopping position. If there exists a universal sink k, then its
rows are all 0 and column all 1 (except (k, k)). Then, if any position in row k or column k is checked (which is not avoidable), the algorithm will eventually converge to (k, |V|) (or (|V |, j) if
k = |V|). Each step of the algorithm will eliminate one node and thus the time to find the only possible sink is O(V). Also, check if the candidate is a sink requires scan its row and column, which is also O(V) and so is the overall time complexity.
22.2-7
For this coloring problem (color the wrestlers “babyface” or “heel”), we proceed by first performing a BFS for each connected component of the graph of wrestlers, where the wrestlers are vertices and an edge exists between each pair of rivalries. Then, we claim that the only possible coloring is to color adjacent layers of BFS trees differently, as otherwise, a vertex will have the same color as its parent in the BFS tree. Then, we just need to check all the edges of the graph to see if the coloring is feasible. The complexity for BFS is O(n + r) and the time for checking is O(r), so the overall complexity is O(n + r).
22.2-9
To traverse all the edges exactly once from both directions, we first build a BFS tree in O(V +E) time to guide the search. Then, we can have the following algorithm: In the algorithm N(u) denotes the neighbors of u in the original graph, N(u) are the neighbors of u in the BFS tree.
For finding a way out of a maze, we can simply use the number of pennies to denote colors in BFS or DFS.
23-1 Second best minimum spanning tree
(a) Consider an arbitrary cut (S, V\S) [in case you did not know: ¡°\¡± is set difference symbol. Read a minus.] of the graph, then the minimum spanning tree must contain the edge with lightest weight of this cut. As all edge weights are distinct, any minimum spanning tree must include this specific edge. As this reasoning holds true for all cuts, there must be exactly one
minimum spanning tree. For uniqueness of the second-best minimum spanning tree, consider the counter example in the figure below.
(b) If there exists a second-best MST that is one edge different from the MST, clearly we can obtain the second-best MST by a single edge swap. Then, the only thing left to show is that no second-best MSTs will be two edges away from the MST. Assume there exists a second- best MST that has edges (x,y), (x¡¯, y¡¯) that are not in MST. Then, let (S, V\S) be the cut defined by removing (x, y) from the second-best MST. Clearly, there exists a lighter weight edge in the cut (the one in MST). Swapping this edge with (x, y), we obtain another spanning tree that has lighter weight than the “second-best MST” yet is still heavier than the MST, so the previous “second-best MST” is not second-best, a contradiction.
(c) Consider the path from u to v in T and let x be the immediate ancestor of v on the path. Then we have w(max[u, v]) = max{w(max[u, x]),w(x, v)}. Then, starting from an arbitrary root of T, we can use this equation to compute max[u, v] among the root and all other vertices in O(V ) time by traversing the tree. We obtain all the max[u, v] values by repeating this for all |V| possible roots.
(d) We first compute the MST T and then use the algorithm in the previous section to compute all max[u, v] values defined on T. Based on part (b), the second-best MST can be obtained by swapping a single edge.
To find the edge, we check for each edge (u, v) the value w(u, v) – w(max[u, v]) as it precisely calculates the least increment of the weight of the tree when we swap the edge (u, v) into the MST. Then, the edge (u, v) with the least increment will be swapped with max[u, v] to obtain the second-best MST. For the time complexity, calculating the MST requires O(E + V log V ) = O(V2) time. computing all max[u, v] values requires O(V2). checking all edges not in T requires O(E) = O(V2) time, so the overall complexity is O(V2).
23-3 Bottleneck spanning tree
(a) Assume not, then there exists a bottleneck spanning tree T whose heaviest edge (u, v) is less than the weight of every edge in the MST T¡¯. Then, we can add (u, v) to T¡¯, which will form a cycle (as both T and T¡¯ are spanning trees). Removing any edge on the cycle (except (u, v)) will result in a spanning tree with smaller weight than T¡¯, contradicting the fact that T¡¯ is the MST. Thus, the bottleneck spanning tree has its weight at least the weight of some edge in the MST. In turn, MST is a bottleneck spanning tree.
(b) We can remove all edges with weight heavier than b and test the connectivity of the remaining graph. If it is still connected, then we have a bottleneck spanning tree with weight at most b (any arbitrary tree in this remaining graph). Otherwise, there’s no such tree. The BFS can be used to find such a tree if it exists and runs in linear (O(V + E)) time.
(c) Finding the bottleneck spanning tree is basically finding the smallest integer b such that
the graph is still connected when all edges with weights larger than b are removed. Once the value b is available, the bottleneck spanning tree can be found in O(V + E) time (part (b)). To find the value b, we can perform binary search using edge weights. Notice that in O(E) time we are able to find the median of all edge weights. Using the median as the input for part (b). We can test whether a bottleneck spanning tree exists. If so, we can remove all edges with weights larger than the median in O(E) time. If not, we can contract all edges with weights smaller than the median in O(E log log V) time. Then we find the median in the new graph and run part (b) again.
Notice that each time we repeat the process, the number of edges is halved. Also, the overall complexity for each step is bounded by O(Et log log V +V ) and we have at most O(logE) = O(log V ) steps (Et is the number of edges at step t). Combining the claims, the overall time complexity is sub-linear, which is O(E log log V + V log V ).