1. The incidence matrix of a directed graph \(G=(V,E)\) with no self-loops is a \(|V|\times|E|\) matrix \(B=(b_{ij})\) such that \[ b_{ij} = \begin{cases} -1 & \text{if edge } j \text{ leaves vertex } i,\\ +1 & \text{if edge } j \text{ enters vertex } i,\\ 0 & \text{otherwise.} \end{cases} \] Describe what the entries of the matrix product \(B B^{\mathsf T}\) represent, where \(B^{\mathsf T}\) is the transpose of \(B\).
2. Show how to use a depth-first search of an undirected graph \(G\) to identify the connected components of \(G\), so that the depth-first forest contains as many trees as \(G\) has connected components. More precisely, show how to modify depth-first search so that it assigns to each vertex \(v\) an integer label \(v.\mathrm{cc}\) between \(1\) and \(k\), where \(k\) is the number of connected components of \(G\), such that \(u.\mathrm{cc} = v.\mathrm{cc}\) iff \(u\) and \(v\) belong to the same connected component.
3. Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. Show that the converse is not true by giving a counterexample.
4. Given a weighted, directed graph \(G=(V,E)\) with no negative-weight cycles, let \(m\) be the maximum over all vertices \(v\in V\) of the minimum number of edges in a shortest path from the source \(s\) to \(v\) (shortest by total weight, not by number of edges). Suggest a simple change to the Bellman–Ford algorithm that allows it to terminate in \(m+1\) passes, even if \(m\) is not known in advance.
5. Consider a directed graph \(G=(V,E)\) in which each edge \((u,v)\in E\) has an associated value \(r(u,v)\in[0,1]\) representing the reliability (probability the channel from \(u\) to \(v\) does not fail). Assume independence. Give an efficient algorithm to find the most reliable path between two given vertices.
6. Show how to express the single-source shortest-paths problem as a product of matrices and a vector. Describe how evaluating this product corresponds to a Bellman–Ford-like algorithm.
7. The Floyd–Warshall algorithm appears to require \(\Theta(n^3)\) space, since it creates \(d_{ij}^{(k)}\) for \(i,j,k=1,2,\dots,n\). Show that the procedure \(\textsc{Floyd–Warshall}'\), which simply drops all the superscripts, is correct, and thus only \(\Theta(n^2)\) space is required.
8. The edge connectivity of an undirected graph is the minimum number \(k\) of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is \(1\), and that of a cyclic chain of vertices is \(2\). Show how to determine the edge connectivity of an undirected graph \(G=(V,E)\) by running a maximum-flow algorithm on at most \(|V|\) flow networks, each having \(O(V+E)\) vertices and \(O(E)\) edges.
9. Suppose pattern \(P\) and text \(T\) are randomly chosen strings of length \(m\) and \(n\), respectively, from the \(d\)-ary alphabet \(\Sigma_d=\{0,1,\dots,d-1\}\) with \(d\ge 2\). Show that the expected number of character-to-character comparisons made by the implicit loop in line 2 of the naive algorithm is \[ (n-m+1)\,\frac{1 - d^{-m}}{1 - d^{-1}} \;\le\; 2(n-m+1) \] over all executions of this loop. (Assume the naive algorithm stops comparing characters for a given shift once it finds a mismatch or matches the entire pattern.) Thus, for randomly chosen strings, the naive algorithm is quite efficient.
10. Show how to extend the Rabin–Karp method to handle the problem of looking for a given \(m\times m\) pattern in an \(n\times n\) array of characters. (The pattern may be shifted vertically and horizontally, but not rotated.)