Detailansicht

Max-Flow Min-Cut
Timon Heiko Thalwitzer
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Betreuer*in
Christian Krattenthaler
Volltext herunterladen
Volltext in Browser öffnen
Alle Rechte vorbehalten / All rights reserved
DOI
10.25365/thesis.2732
URN
urn:nbn:at:at-ubw:1-30260.30850.298264-1
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract
(Deutsch)
Die vorliegende Arbeit ist eine Monographie über Netzwerke. Die Theorie der Netzwerkflüsse ist ein mathematisches Gebiet, das weitverbreitete Anwendung findet in Feldern wie Ökonomie, Verkehrs- und Städteplanung, Telekommunikation und vielen anderen mehr. Aus mathematischer Sicht ist es interessant, dass Netzwerke gleichermaßen mit Methoden der Graphentheorie, als auch mit solchen aus der linearen Programmierung behandelt werden können. Im Grunde behandelt der vorliegende Text eine bestimmte Art von linearen Programmen, die eine sehr spezifische Struktur aufweisen. Jeder dieser scheinbar unterschiedlichen Zugänge hat seine Vor- und Nachteile. Netzwerke und Netzwerflüsse stellen ausführlich behandelte Begriffe dar, und sind seit den 1950ern Gegenstand einer intensiven Forschungstätigkeit. Ein umfangreicher Bestand an Literatur zu sowohl Netzwerkflüssen als auch zur linearen Programmierung ist heute verfügbar. In dieser Diplomarbeit behandle ich vor allem das Max-Flow Min-Cut Theorem, als auch verschiedene Algorithmen, die zum Auffinden von maximalen Netzwerkflüssen dienen. Ich versuche dabei, die kombinatorische Herangehensweise und jene von der linearen Programmierung herkommende so homogen wie möglich zu präsentieren und dabei eine Notation zu verwenden, die beiden Zugängen gerecht wird. Ein Aspekt der etwas ungewöhnlich erscheinen könnte ist, dass ich alle Definitionen und Sätze unter Verwendung eines sehr allgemeinen Netzwerkbegriffs formuliere, während in den meisten Arbeiten zu diesem Thema ein engerer Netzwerkbegriff verwendet wird, welcher dazu dienen soll, die Beweise und Rechnungen kürzer zu halten. Da die allgemeinere Definition leicht auf die speziellere zurückgeführt werden kann, ergibt sich durch meine Vorgehensweise keinesfalls der Gewinn neuer oder unbekannter Sätze. Jedoch ließen sich alle Beweise auf sehr natürliche Weise verallgemeinern ohne dabei komplizierter zu werden, und deshalb erschien es mir sinnvoll, das Thema in dieser Art und Weise darzustellen.
Abstract
(Englisch)
This is a monograph on network flows. Network flow theory constitutes a widely applied mathematical field, which is used in practice in fields like economics, traffic routing, urban planning, telecommunication, and countless more. From a mathematical point of view, it is interesting that networks can be treated equally well by methods from graph theory and from linear programming. In fact, this text deals with a certain kind of linear programs with a fairly specific structure. Both of these seemingly different approaches have their advantages and disadvantages. Networks and flows are thoroughly studied notions, and there has been done a lot of research on them since the 1950s. A vast body of literature on both network flows and linear programming exists. In this thesis, I focus on the Max-Flow Min-Cut Theorem, as well as on describing various algorithms for constructing maximal flows in a given network. I also try to present the combinatorial and the linear programming point of view as homogeneous as possible, using a notation that lends itself well to both. One aspect that might appear a little unusual is that I formulated all definitions and theorems using throughout a fairly general network model, whereas in most works done on this topic, a more restricted definition for networks is used, with the aim of keeping the proofs and calculations shorter. Since the more general case can easily be reduced to the more specific one, my approach constitutes by no means the gain of new or unknown theorems. But all of the proofs extended very naturally to the generalizations without becoming more complicated, and hence it made sense to me to present the material in this way.

Schlagwörter

Schlagwörter
(Englisch)
networks network flows max-flow min-cut linear programming duality graph theory combinatorics
Schlagwörter
(Deutsch)
Netzwerk Netzwerfluss Max-Flow Min-Cut Lineare Programmierung Dualität Graphentheorie Kombinatorik
Autor*innen
Timon Heiko Thalwitzer
Haupttitel (Englisch)
Max-Flow Min-Cut
Paralleltitel (Deutsch)
Max-Flow Min-Cut
Publikationsjahr
2008
Umfangsangabe
131 S. : Ill., graph. Darst.
Sprache
Englisch
Beurteiler*in
Christian Krattenthaler
Klassifikation
31 Mathematik > 31.12 Kombinatorik, Graphentheorie
AC Nummer
AC07152346
Utheses ID
2363
Studienkennzahl
UA | 405 | | |
Universität Wien, Universitätsbibliothek, 1010 Wien, Universitätsring 1