In this diploma thesis the maximum flow problem is presented and investigated. Instances of this problem can in various practical situations. Some of these examples are presented in the thesis. The maximum flow problem is introduced and it is shown, that it always has an optimal solution. The concept of a minimal cut is defined and its connection to the maximum flow problem is investigated. In the second part of the diploma thesis some of the well known algorithms for searching the maximum flow are treated. First the Ford - Fulkerson algorithm is presented, than we concentrate mostly on the Edmonds - Karp algorithm and Goldberg - Tarjan algorithm. For each of these two algorithms the time complexity and the important characteristics are analyzed. Their operation is illustrated with a few concrete examples.
|
