(a) Given a flow network G = (V, E, s, t) with positive integer capacities Cuv,...

Transcribed Image Text:

(a) Given a flow network G = (V, E, s, t) with positive integer capacities Cuv, let d = min(u,v) EE Cuv. Either prove or disprove that the value of the maximum flow is an integer multiple of d. (b) Given a flow network G=(V, E, s, t) with positive integer capacities Cuv, let d = GCD({Cuv | (u, v) E E}). Either prove or disprove that the value of the maximum flow is an integer multiple of d. (c) Vertex cover SC V of a graph G = (V, E) is defined as the set of vertices such that every edge in the graph is incident to at least one of the vertices from the set S. The minimum vertex cover problem is to find an S with the maximum size. Give an integer linear program for the vertex cover problem. (a) Given a flow network G = (V, E, s, t) with positive integer capacities Cuv, let d = min(u,v) EE Cuv. Either prove or disprove that the value of the maximum flow is an integer multiple of d. (b) Given a flow network G=(V, E, s, t) with positive integer capacities Cuv, let d = GCD({Cuv | (u, v) E E}). Either prove or disprove that the value of the maximum flow is an integer multiple of d. (c) Vertex cover SC V of a graph G = (V, E) is defined as the set of vertices such that every edge in the graph is incident to at least one of the vertices from the set S. The minimum vertex cover problem is to find an S with the maximum size. Give an integer linear program for the vertex cover problem.

Answer rating: 100% (QA)

a The statement is true and we can prove it using the MaxFlow MinCut Theorem and the concept of Integral Flow First lets define an Integral Flow as a flow in which the flow values on all edges are int... View the full answer