In the following graph from Monday's lecture notes, suppose that the edge weights are the bandwidths of links in a computer network. As the lecture notes explain, paths in a maximum spanning tree of this graph can be used to connect any two vertices of the graph, maximizing the bandwidth of the path (which equals the minimum weight of the edges used by the path).
163 students only: Find the path that would be found in this way between the vertices at the top left and the bottom right of the graph, colored red in the figure. What is the bandwidth of your path?
163 students only: Find another path of the same bandwidth between these same two vertices that does not come from a maximum spanning tree.
265 students only: Given a graph and a number \(x\), suppose we want to test whether all pairs of vertices can be connected by paths of bandwidth \(\ge x\). One way to do it would be to find a maximum spanning tree and compare its smallest edge weight to \(x\). Describe a different way of solving this problem, using algorithms that we have already described, in linear time. (Do not use the linear-time randomized minimum spanning tree algorithm; this problem is simpler than that.)
The cut property of minimum spanning trees states that, if an edge \(e\) is the shortest edge across some cut in a graph (with distinct edge weights), then \(e\) belongs to the minimum spanning tree. A form of the reverse implication is also true: If an edge \(e\) belongs to the minimum spanning tree of a graph, then the graph has a cut for which \(e\) is the shortest crossing edge. Explain why.
Suppose that the weights on the edges of a graph are integers in the range from \(1\) to \(k\), where \(k\) is much smaller than \(n\). For priorities in this range, a priority queue data structure called a bucket queue can handle changes of priority in constant time, and operations that find and remove the minimum-priority item in time \(O(k)\). What is the time bound for JarnÃk's algorithm using this data structure?
A "source vertex" in a directed graph is defined to be a vertex with no incoming edges. If there is more than one source vertex in a DAG, any one of them could be the first vertex in a topological ordering of the DAG. Suppose that \(v\) is a source vertex in a DAG \(G\). Explain how to modify the order of vertices in the outer loop of the reverse-postorder algorithm for topological sorting so that \(v\) ends up first in the topological order. (The outer loop is the line "for each vertex \(v\) in \(G\)" in the pseudocode from the lecture notes.)