Q)a)(T/F) Suppose that a flow network G = (V,E) violates the assumption that the network contains a path s ?v? t for all vertices v ? V. Let u be a vertex for which there is no path s ?u? t. There must exist a maximum flow f in G such that f(u,v) = f(v,u) = 0 for all vertices v ? V, which means it is safe to remove such vertices and their incident edges without changing the maximum flow.

b)(T/F) In union-by-rank heuristic of disjoint sets, When MAKE-SET creates a singleton set, the single node in the corresponding tree has an initial rank of 0. Each FIND-SET operation leaves all ranks unchanged. The UNION operation makes the root with higher rank the parent of the root with lower rank and increment the parents rank by 1. We can prove that every node has rank O(logn) using this heuristic.