# Question: A path cover of a directed graph G V

A path cover of a directed graph G = (V, E) is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P. Paths may start and end anywhere, and they may be of any length, including 0. A minimum path cover of G is a path cover containing the fewest possible paths.

a. Give an efficient algorithm to find a minimum path cover of a directed acyclic graph G = (V, E). (Hint: Assuming that V = {1, 2, . . . ,n}, construct the graph G' = (V', E'), where

b. and run a maximum-flow algorithm.)

c. Does your algorithm work for directed graphs that contain cycles? Explain.

a. Give an efficient algorithm to find a minimum path cover of a directed acyclic graph G = (V, E). (Hint: Assuming that V = {1, 2, . . . ,n}, construct the graph G' = (V', E'), where

b. and run a maximum-flow algorithm.)

c. Does your algorithm work for directed graphs that contain cycles? Explain.

## Answer to relevant Questions

Let G = (V, E) be a flow network with source s, sink t, and integer capacities. Suppose that we are given a maximum flow in G. a. Suppose that the capacity of a single edge (u, v) ¬ E is increased by 1. Give an O (V ...Prove that a comparison network with n inputs correctly sorts the input sequence ¬n, n - 1,..., 1¬ if and only if it correctly sorts the n - 1 zero-one sequences ¬1, 0, 0,..., 0, 0¬, ¬1, 1, ...Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G, and if d[u] < d[v] in a depth-first search of G, then v is a descendant of u in the depth-first forest produced.A directed graph G = (V, E) is said to be semi connected if, for all pairs of vertices u, v ¬ V, we have u →v or v→ u. Give an efficient algorithm to determine whether or not G is semi connected. Prove ...Calculate the reversible work and irreversibility for the process described in Problem 5.65, assuming that the heat transfer is with the surroundings at20C.Post your question