In this chapter, we focus on flows through directed graphs called networks. While graph theory is an enormous area of math (in which I work), we are particularly interested in optimization problems on weighted and or capacitated networks, such as maximizing the flow through a network with limited capacity, or finding a path minimizing the distance between nodes.
In Section 7.1 we explore maximal flows through capacitated networks and model this problem with linear optimization. In Section 7.2 we discuss the dual problem, connect it to cuts in the network, and discuss algorithms which solve both problems. In Section 7.3 we shift our attention to weighted networks, and examine shortest paths and minimum cost flows.
