Graph Theory Lecture Notes: Flows and Cuts in Networks

From IFORS Education Resources
Jump to: navigation, search

By: Bill Cherowitzo

Flows and Cuts in Networks

A capacitated single source-single sink network is a directed graph D, with each arc (i, j) assigned a positive real number cij called the capacity of the arc, and two distinguished vertices called a sink (t) and a source (s). The source has out-degree of at least one and the sink has in-degree of at least one. (In almost all of the examples we consider the source will have in-degree of 0 and the sink will have out-degree of 0, but this is not required in the definition.) We shall refer to these as (s,t)-networks.

Link to material:

Personal tools