Graphs and Network Flow

Question 1

What are the generic loop invariants used for searching a graph starting from some node s

Answer 1

Generic loop invariants:
Nodes are considered to be not found, found, not handled, handled

Question 2

If Found:

If Handled:

Answer 2

if node v is found, we can trace a path from s to the node, can be traced backwards.
v, π(v), π(π(v)), π(π(π(v))), . . . , s.

If node v is handled, all neighbours have been found.

Question 3

Extra LI for BFS

Answer 3

Nodes have been found in order of their distance from s.

Question 4

Extra LI for DFS

Answer 4

Nodes in the stack form a path starting at s going to the current node u being considered

Question 5

Recursive DFS pre + post cons

Answer 5

Pre: A directed or undirected graph is given, some nodes marked found and some node s’ specified
Post: Every node reachable from s’ is found

Question 6

Extra LI for Dijkstra’s shortest-weighted paths alg

Answer 6

Extra LI are
- Handled: For each handled node v, the values of d(v) and pi(v) give the shortest length and path from s. (Path only contains handled nodes).

• Found: For each unhandled node v, the values of d( v) and pi(v) give the shortest length and path from s.
  Visit any number of handled nodes starting from s, then follow one last node that may or not be handled.

Question 7

What data structure does Dijkstra’s alg use?

Answer 7

Priority Queue

Question 8

Steps for Network flow Diagram

Answer 8

Given flow - > Augmenting Graph -> Augmenting path - > New flow
Repeat until augmenting graph no longer has a augmenting path

Question 9

How to make cut

Answer 9

Cut such that flow out of ‘s’ node = flow into cut ‘u’.

Question 10

How do you get New flow values?

Answer 10

On the augmenting graph path, find the bottle neck ‘w’ value. Add/subtract if passing through or backward on each node on the path.

Question 11

Capacity of cut = ?

Answer 11

= Capacity of edges crossing from U to V.

Question 12

Conclusion to network flow solution

Answer 12

All edges across the cut are at capacity in flow. Any edges going from V to U have no flow in them.
Hence, the flow across the cut equals flow out of s in the final Flow equals capacity of the cut.
Rate of final flow = #

Question 13

Flow witness statements

Answer 13

The flow witnesses the fact that a flow with rate 16 is obtainable.
The cut witnesses the fact that a flow can be no bigger than 16
Hence a max flow of 16 is optimal.