MAS341: Graph Theory

1.

For the graph in Figure 3.7.1, use Kruskal's algorithm (“avoid cycles”) to find a minimum weight spanning tree. Your answer should include a complete list of the edges, indicating which edges you take for your tree and which (if any) you reject in the course of running the algorithm.

2.

For the graph in Figure 3.7.1, use Prim's algorithm (“build tree”) to find a minimum weight spanning tree. Your answer should list the edges selected by the algorithm in the order they were selected.

3.

For the graph in Figure 3.7.2, use Kruskal's algorithm (“avoid cycles”) to find a minimum weight spanning tree. Your answer should include a complete list of the edges, indicating which edges you take for your tree and which (if any) you reject in the course of running the algorithm.

4.

For the graph in Figure 3.7.2, use Prim's algorithm (“build tree”) to find a minimum weight spanning tree. Your answer should list the edges selected by the algorithm in the order they were selected.

5.

For the graph in Figure 3.7.3, use Kruskal's algorithm (“avoid cycles”) to find a minimum weight spanning tree. Your answer should include a complete list of the edges, indicating which edges you take for your tree and which (if any) you reject in the course of running the algorithm.

6.

For the graph in Figure 3.7.3, use Prim's algorithm (“build tree”) to find a minimum weight spanning tree. Your answer should list the edges selected by the algorithm in the order they were selected.

7.

A new local bank is being created and will establish a headquarters \(h\text{,}\) two branches \(b_1\) and \(b_2\text{,}\) and four ATMs \(a_1\text{,}\) \(a_2\text{,}\) \(a_3\text{,}\) and \(a_4\text{.}\) They need to build a computer network such that the headquarters, branches, and ATMs can all intercommunicate. Furthermore, they will need to be networked with the Federal Reserve Bank of Atlanta, \(f\text{.}\) The costs of the feasible network connections (in units of $10,000) are listed below:

The bank wishes to minimize the cost of building its network (which must allow for connection, possibly routed through other nodes, from each node to each other node), however due to the need for high-speed communication, they must pay to build the connection from \(h\) to \(f\) as well as the connection from \(b_2\) to \(a_3\text{.}\) Give a list of the connections the bank should establish in order to minimize their total cost, subject to this constraint. Be sure to explain how you selected the connections and how you know the total cost is minimized.

8.

A disconnected weighted graph obviously has no spanning trees. However, it is possible to find a spanning forest of minimum weight in such a graph. Explain how to modify both Kruskal's algorithm and Prim's algorithm to do this.

9.

Prove Proposition 3.2.3.

10.

In the paper where Kruskal's algorithm first appeared, he considered the algorithm a route to a nicer proof that in a connected weighted graph with no two edges having the same weight, there is a unique minimum weight spanning tree. Prove this fact using Kruskal's algorithm.

11.

Use Dijkstra's algorithm to find the distance from \(a\) to each other vertex in the digraph shown in Figure 3.7.4 and a directed path of that length.

12.

Table 3.7.5 contains the length of the directed edge \((x,y)\) in the intersection of row \(x\) and column \(y\) in a digraph with vertex set \(\{a,b,c,d,e,f\}\text{.}\) For example, \(w(b,d)=21\text{.}\) (On the other hand, \(w(d,b)=10\text{.}\)) Use this data and Dijkstra's algorithm to find the distance from \(a\) to each of the other vertices and a directed path of that length from \(a\text{.}\)

13.

Use Dijkstra's algorithm to find the distance from \(a\) to each other vertex in the digraph shown in Figure 3.7.6 and a directed path of that length.

14.

Table 3.7.7 contains the length of the directed edge \((x,y)\) in the intersection of row \(x\) and column \(y\) in a digraph with vertex set \(\{a,b,c,d,e,f\}\text{.}\) For example, \(w(b,d)=47\text{.}\) (On the other hand, \(w(d,b)=6\text{.}\)) Use this data and Dijkstra's algorithm to find the distance from \(a\) to each of the other vertices and a directed path of that length from \(a\text{.}\)

15.

Give an example of a digraph having an undirected path between each pair of vertices, but having a root vertex \(r\) so that Dijkstra's algorithm cannot find a path of finite length from \(r\) to some vertex \(x\text{.}\)

16.

Notice that in our discussion of Dijkstra's algorithm, we required that the edge weights be nonnegative. If the edge weights are lengths and meant to model distance, this makes perfect sense. However, in some cases, it might be reasonable to allow negative edge weights. For example, suppose that a positive weight means there is a cost to travel along the directed edge while a negative edge weight means that you make money for traveling along the directed edge. In this case, a directed path with positive total weight results in paying out to travel it, while one with negative total weight results in a profit.

1. Give an example to show that Dijkstra's algorithm does not always find the path of minimum total weight when negative edge weights are allowed.

2. Bob and Xing are considering this situation, and Bob suggests that a little modification to the algorithm should solve the problem. He says that if there are negative weights, they just have to find the smallest (i.e., most negative weight) and add the absolute value of that weight to every directed edge. For example, if \(w(x,y)\geq -10\) for every directed edge \((x,y)\text{,}\) Bob is suggesting that they add \(10\) to every edge weight. Xing is skeptical, and for good reason. Give an example to show why Bob's modification won't work.