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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:7507 |
| Date | 01 May 2013 |
| Creators | Marcon, Alister Justin |
| Source Sets | South African National ETD Portal |
| Detected Language | English |
| Type | Thesis |
| Rights | University of Johannesburg |
Page generated in 0.0021 seconds