Lade Inhalt...

Ein experimenteller Vergleich von zwei Algorithmen zur Berechnung des maximalen Flusses in einem asymmetrischen Netzwerk mit reellen Kapazitäten

©1997 Diplomarbeit 177 Seiten

Zusammenfassung

Inhaltsangabe:Problemstellung:
In der vorliegenden Arbeit wird das Problem der Berechnung eines maximalen Flusses in einem gerichteten Netzwerk mit nicht negativen, reellwertigen Kantenkapazitäten betrachtet und eine PASCAL-Implementierung für ein asymmetrisches Netzwerk mit diesen Eigenschaften angegeben. Das Hauptaugenmerk liegt dabei in der Betrachtung verschiedener Methoden zur Berechnung einer wesentlichen Teilaufgabe des Gesamtproblems, nämlich der Berechnung blockierender Flüsse. Es werden zwei grundsätzlich verschiedene Verfahren hierzu angegeben, aus welchen dann jeweils zwei Implementierungen fließen. Insgesamt werden folglich die Laufzeiten von vier Implementierungen verglichen.

Inhaltsverzeichnis:Inhaltsverzeichnis:
1.GRUNDLAGEN AUS DER GRAPHENTHEORIE1
2.GRUNDLAGEN AUS DER FLUSSTHEORIE5
2.1.Grundlegende Definitionen sowie ein Verfahren zur Berechnung maximaler Flüsse in Netzwerken5
2.2.Eine PASCAL-Implementierung für 2.112
3.BLOCKIERENDE FLÜSSE22
3.1.Ein Verfahren zur Berechnung blockierender Flüsse mittels höhenbalancierter Bäume22
3.1.1.Herleitung des Verfahrens22
3.1.2.Eine PASCAL-Implementierung für 3.1.134
3.1.3.Eine PASCAL-Implementierung mit Rot-Schwarz-Bäumen für 3.1.158
3.2.Ein Verfahren zur Berechnung blockierender Flüsse mittels unbalancierter Bäume65
3.2.1.Herleitung des Verfahrens65
3.2.2.Eine PASCAL-Implementierung für 3.2.171
3.2.3.Eine Veränderung des Verfahrens aus 3.2.183
3.2.4.Eine statisch gewichtete Version86
3.3.Ergebnisse aus Laufzeittests89
Anhang: menügesteuerte Komplettversion für PC-80x86 unter MS-DOS
Eidesstattliche Erklärung

Leseprobe

Inhaltsverzeichnis


Details

Seiten
Erscheinungsform
Originalausgabe
Jahr
1997
ISBN (eBook)
9783832403737
ISBN (Paperback)
9783838603735
Dateigröße
4.5 MB
Sprache
Deutsch
Institution / Hochschule
Universität des Saarlandes – unbekannt
Erscheinungsdatum
2014 (März)
Schlagworte
vergleich algorithmen berechnung flusses netzwerk kapazitäten
Zurück

Titel: Ein experimenteller Vergleich von zwei Algorithmen zur Berechnung des maximalen Flusses in einem asymmetrischen Netzwerk mit reellen Kapazitäten
book preview page numper 1
book preview page numper 2
book preview page numper 3
book preview page numper 4
book preview page numper 5
book preview page numper 6
book preview page numper 7
book preview page numper 8
book preview page numper 9
book preview page numper 10
book preview page numper 11
book preview page numper 12
book preview page numper 13
book preview page numper 14
book preview page numper 15
book preview page numper 16
book preview page numper 17
book preview page numper 18
book preview page numper 19
book preview page numper 20
book preview page numper 21
book preview page numper 22
book preview page numper 23
book preview page numper 24
book preview page numper 25
book preview page numper 26
book preview page numper 27
book preview page numper 28
book preview page numper 29
book preview page numper 30
book preview page numper 31
book preview page numper 32
book preview page numper 33
book preview page numper 34
book preview page numper 35
book preview page numper 36
book preview page numper 37
177 Seiten
Cookie-Einstellungen