This and the next chapter discuss flows in networks. A network is defined as a directed graph G with edge capacities and two specified vertices s (source) and t (sink). The goal is to transport as many units as possible from s to t, which is called a maximum flow. A flow is a function assigning values to edges such that the flow on each edge does not exceed its capacity. The excess of a flow at a vertex is the difference between incoming and outgoing flows. A flow satisfying the flow conservation rule (excess zero at all vertices except s and t) is an s-t-flow, with its value defined as the negative of the excess at the source. The problem has applications, such as the job assignment problem, where we aim to minimize the total time to complete all jobs. This problem can be transformed into a flow problem, where we find flows that satisfy certain constraints. The solution involves binary search and modeling the problem as a flow network. Section 8.1 introduces the maximum flow problem and proves the Max-Flow-Min-Cut Theorem, which relates maximum flows to minimum cuts. It also shows that for integral capacities, there exists an integral maximum flow. This result implies Menger's Theorem on disjoint paths. Sections 8.3–8.5 present efficient algorithms for maximum flow. Section 8.6 discusses storing minimum cut capacities for all vertex pairs, while Section 8.7 shows how to compute edge-connectivity more efficiently. The chapter concludes with the LP formulation of the maximum flow problem and a proposition that guarantees the existence of an optimal solution. The text emphasizes the development of combinatorial algorithms rather than linear programming methods.This and the next chapter discuss flows in networks. A network is defined as a directed graph G with edge capacities and two specified vertices s (source) and t (sink). The goal is to transport as many units as possible from s to t, which is called a maximum flow. A flow is a function assigning values to edges such that the flow on each edge does not exceed its capacity. The excess of a flow at a vertex is the difference between incoming and outgoing flows. A flow satisfying the flow conservation rule (excess zero at all vertices except s and t) is an s-t-flow, with its value defined as the negative of the excess at the source. The problem has applications, such as the job assignment problem, where we aim to minimize the total time to complete all jobs. This problem can be transformed into a flow problem, where we find flows that satisfy certain constraints. The solution involves binary search and modeling the problem as a flow network. Section 8.1 introduces the maximum flow problem and proves the Max-Flow-Min-Cut Theorem, which relates maximum flows to minimum cuts. It also shows that for integral capacities, there exists an integral maximum flow. This result implies Menger's Theorem on disjoint paths. Sections 8.3–8.5 present efficient algorithms for maximum flow. Section 8.6 discusses storing minimum cut capacities for all vertex pairs, while Section 8.7 shows how to compute edge-connectivity more efficiently. The chapter concludes with the LP formulation of the maximum flow problem and a proposition that guarantees the existence of an optimal solution. The text emphasizes the development of combinatorial algorithms rather than linear programming methods.