maths.free › Combinatorics & Graph Theory › 12. Graph Algorithms › Graph Algorithms: exercises
Graph Algorithms: exercises
Graph Algorithms: exercises — from Keller & Trotter, Applied Combinatorics.
Practice (15)
Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.
-
For the graph in , 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.
-
For the graph in , 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.
-
For the graph in , 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.
-
For the graph in , 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.
-
For the graph in , 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.
-
For the graph in , 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.
-
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.
-
Prove .
-
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.
-
Use Dijkstra's algorithm to find the distance from \(a\) to each other vertex in the digraph shown in and a directed path of that length.
-
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\}\). For example, \(w(b,d)=21\). (On the other hand, \(w(d,b)=10\).) 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\).
-
Use Dijkstra's algorithm to find the distance from \(a\) to each other vertex in the digraph shown in and a directed path of that length.
-
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\}\). For example, \(w(b,d)=47\). (On the other hand, \(w(d,b)=6\).) 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\).
-
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\).
-
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.
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.
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 (, 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)\), 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.
Symbols used here
Inequalities that allow equality; < and > exclude it.
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
Number of k-element subsets of n things: n!/(k!(n−k)!).
Add a_k for k = 1 up to n.
Multiply a_k for k = 1 up to n.
The set with no elements; the number of elements of A.
Questions people ask
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Prófaðu þitt eigið
Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.
Meira í Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs