Graphen Algorithmen Netze

Dr. Firoz Kaderali ist Professor für Kommunikationssysteme an der Fern-Universität Hagen.Dr. rer. nat. Werner Poguntke ist Professor für Informatik an der Märkischen Fachhochschule Iserlohn.

• 1 Grundbegriffe.- 1.1 Pseudographen, Multigraphen, Graphen.- 1.2 Wege, Kreise, Zusammenhang.- 1.3 Kreise und Schnitte.- 2 Darstellung von Graphen.- 2.1 Diagramme und Planarität.- 2.2 Matrizen.- 3.3 Weitere Matrizen und deren Eigenschaften.- 3 Algorithmen.- 3.1 Das Erkennen und Suchen von Bäumen.- 3.2 Algorithmen und deren Komplexität.- 3.3 Weitere Algorithmen und Begriffe.- 4 Pseudodigraphen.- 4.1 Grundbegriffe.- 4.2 Multidigraphen und Matrizen.- 5. Bewertungen.- 5.1 Ecken-, Kanten- und Bogenbewertungen.- 5.2 Die algebraische Struktur von Bewertungen.- 6 Kürzeste Wege und minimale Gerüste.- 6.1 Kürzeste Wege.- 6.2 Minimale Gerüste.- 7 Flüsse.- 7.1 Einführung.- 7.2 Die Sätze von Ford und Fulkerson.- 7.3 Der Satz von Edmonds und Karp.- 7.4 Eine kombinatorische Anwendung: Der Satz von Menger.- 7.5 Weitere kombinatorische Anwendungen.- 7.6 Zulässige Flüsse und Zirkulationen.- 7.7 Synthese minimaler Netze.- 8 Wegeauswahl in Netzen.- 8.1 Das Problem der Wegeauswahl in Kommunikationsnetzen.- 8.2 Algorithmen zur Bestimmung kürzester Wege.- 8.3 Das Stabilitätsproblem bei der Nutzung kürzester Wege.- 8.4 Zur Übertragung von Routing-Informationen.- 8.5 Das Routing im ARPANET und im TYMNET.- 8.6 Das Routing im Zeichengabesystem Nr. 7.- 8.7 Optimales Routing.- 9 Zuverlässigkeit von Netzen.- 9.1 Einführung.- 9.2 Der Zusammenhang von Zufallsgraphen.- 9.3 Zuverlässigkeitsmaße und -polynome.- 9.4 Zur Komplexität des Zuverlässigkeitsproblems.- 9.5 Abschätzungen für das Zuverlässigkeitspolynom.- 9.6 Routing und Zuverlässigkeit.- 9.7 Synthese extremaler Netze.- 10 Einige graphentheoretische Aspekte des VLSI-Layout.- 10.1 Programmierbare Logikfelder (PLA).- 10.2 Alternierende Kreise in gemischten Graphen.- 10.3 Das Matrix-Permutationsproblem.- 10.4 Färbungen,Cliquen und Intervallgraphen.- 10.5 Zur Säuberung von Bäumen.- A Verwendete Begriffe und Symbole aus der Mengenlehre.- B Erläuterung der verwendeten Begriffe aus der Linearen Algebra.- C Erläuterung der verwendeten Begriffe aus der Theorie der Matrizen.- D Pascal-Programme zu den Algorithmen von Dijkstra und von Kruskal.- E Pascal-Programm zum Algorithmus von Ford und Fulkerson.- F Boolesche Ausdrücke.- G Gerüste eines Graphen.- H Ein Pascal-Programm zur Berechnung des Zuverlässigkeitspolynoms.- I Lösungen zu den Aufgaben.