Directed/undirected connectivity and flow networks, terminology and representations; Counting routes, shortest/longest routes with restrictions; Minimum spanning trees using greedy/Prim algorithms; Maximum flow with capacities and contextual limitations
Example 1
Roads AB=2,BC=5,AC=9km. Find the shortest A–C route length.
Show worked answer
Answer: 7
- Compare direct AC with AB+BC. The route through B is 2km shorter.
Example 2
An undirected triangle network has edge weights 6,2,10. Find a minimum spanning tree’s total weight.
Show worked answer
Answer: 8
- Choose the two lighter edges, connecting all three vertices without a cycle.
Example 3
Directed arcs S→A and S→B have capacities 2 and 3. Arcs A→T and B→T have the same respective capacities, with no other arcs. Find the maximum S–T flow.
Show worked answer
Answer: 5
- The two independent paths carry a and b units; their sum also equals the capacity of the cut leaving S.