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: http://www-math.ucdenver.edu/~wcherowi/courses/m4408/gtaln11.html


Personal tools