Abstract
M.Sc. (Mathematics)
In Chapter 1, we consider the relevant theory pertaining to graphs and digraphs
that will be used in the study of flows in networks. Warshall’s algorithm for
reachability is also considered since it will allow us to ascertain whether some
paths exist in some instance.
In Chapter 2, we explore flows and cuts in networks. We define the basic concepts
of source, sink, intermediate vertices, capacity, costs and lower-bounds.
Feasible flows are defined, as well as the value of a flow. Cuts in capacitated
networks are explored and further theory relating the value of a flow and cuts is
given. We considered the problem of determining a maximal flow. In particular,
we consider augmentations of the flow—this allows us to give a characterization
of a maximal flow. The important Max-flow Min-cut theorem is also considered.
After having explored the relevant theory, we move on to methods of finding
a maximal flow for a given s-t network that has a capacity on each of its
arcs. Firstly, we consider zero-one and unit-capacity networks since these play
a role in the applications of maximal flows in Chapter 4. We, then, compile
the relevant theory and algorithms in order to implement two augmenting path
finding algorithms.