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.

Umfassendes Lehrbuch zu einem modernen Gebiet der digitalen Vermittlungs- und Datentechnik.Das Buch wendet sich an Studenten der Elektrotechnik und bereitet für diesen Studiengang die Grundlagen aus den Nachbardisziplinen Mathematik und Informatik auf, um die für die Elektrotechnik bedeutsamen Anwendungen in der Kommunikationstechnik und im Chip-Design (Entwurf mikroelektronischer Schaltungen) darzustellen.Das Buch entstand aus Vorlesungen an der TH Darmstadt und aus Kursen der FernUniversität Hagen.

Ein umfassendes Lehrbuch zu einem modernen Gebiet der digitalen Vermittlungs- und Datentechnik.
Das Buch wendet sich an Studenten der Elektrotechnik und bereitet für diesen Studiengang die Grundlagen aus den Nachbardisziplinen Mathematik und Informatik auf, um die für die Elektrotechnik bedeutsamen Anwendungen in der Kommunikationstechnik und im Chip-Design (Entwurf mikroelektronischer Schaltungen) darzustellen.
Das Buch entstand aus Vorlesungen an der TH Darmstadt und aus Kursen der Fernuniversität Hagen.

Umfassendes Lehrbuch zu einem modernen Gebiet der digitalen Vermittlungs- und Datentechnik.Das Buch wendet sich an Studenten der Elektrotechnik und bereitet für diesen Studiengang die Grundlagen aus den Nachbardisziplinen Mathematik und Informatik auf, um die für die Elektrotechnik bedeutsamen Anwendungen in der Kommunikationstechnik und im Chip-Design (Entwurf mikroelektronischer Schaltungen) darzustellen.Das Buch entstand aus Vorlesungen an der TH Darmstadt und aus Kursen der FernUniversität Hagen.

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.