Analysis of algorithms

Written response only

QUESTION 1 Which of the tollowing claims are true and which are faise. Justity your answer by glving elther a (short) proof or a (e) In any maximum flow there are no directed cydles that carry positive flow. (A cycle (e1 ,..., sk) carries posiltive flow if f (01)>0,..., (ex)>0.) (b) There always exists a maximum flow without cycles carrying positive flow (c) If all edges in a graph have distinct capacities, there is a unique maximum flow. (d) In a directed graph with at most one edge between each pair of vertices, if we replace each directed edge by an undirected edge, the maximum flow remains unchanged. (e). If we multiply all edge capacities by a positive number A, the minimum cut remains unchanged (f ) If we add a positive number A to all edge capacities, the minimum cut remains unchanged. a positive number A to all edge capacities, the maximum flow increases by a multiple of A. Arial3(12p) T