91Ó°ÊÓ

True or false? Any matching is contained in a maximal matching. If true, prove it; if false, give a counterexample.

Refer to a network \(G\) that, in addition to having nonnegative integer capacities \(C_{i j}\), has nonnegative integer minimal edge flow requirements \(m_{i j} .\) That is, a flow \(F\) must satisfy $$m_{i j} \leq F_{i j} \leq C_{i j}$$ for all edges \((i, j)\) Show that if a flow exists in \(G,\) a maximal flow exists in \(G\) with value \(\min \\{C(P, \bar{P})-m(\bar{P}, P) \mid(P, \bar{P})\) is a cut in \(G\\}\)

Refer to a network \(G\) that, in addition to having nonnegative integer capacities \(C_{i j}\), has nonnegative integer minimal edge flow requirements \(m_{i j} .\) That is, a flow \(F\) must satisfy $$m_{i j} \leq F_{i j} \leq C_{i j}$$ for all edges \((i, j)\) Show that if a flow exists in \(G,\) a minimal flow exists in \(G\) with value \(\max \\{m(P, \bar{P})-C(\bar{P}, P) \mid(P, \bar{P})\) is a cut in \(G\\}\)

Refer to a network \(G\) that, in addition to having nonnegative integer capacities \(C_{i j}\), has nonnegative integer minimal edge flow requirements \(m_{i j} .\) That is, a flow \(F\) must satisfy $$m_{i j} \leq F_{i j} \leq C_{i j}$$ for all edges \((i, j)\) Assume that \(G\) has a flow \(F\). Develop an algorithm for finding a minimal flow in \(G\).

True or false? If \(F\) is a flow in a network \(G\) and \((P, \bar{P})\) is a cut in \(G\) and the capacity of \((P, \bar{P})\) exceeds the value of the flow, \(F,\) then the cut \((P, \bar{P})\) is not minimal and the flow \(F\) is not maximal. If true, prove it; otherwise, give a counterexample.