Graphen Algorithmen Netze

Frontmatter

1. Grundbegriffe

Zusammenfassung

Ein Pseudograph ist ein Tripel P = (E, K, v) bestehend aus einer Eckenmenge E, einer Kantenmenge K und einer (Inzidenz-) Abbildung

$$ v:K \to \left\{ {\{ x,y\} \left| {x,y \in E} \right.} \right\} $$

Firoz Kaderali, Werner Poguntke

2. Darstellung von Graphen

Zusammenfassung

Schon im ersten Abschnitt war von Diagrammen — also zeichnerischen Darstellungen von Pseudographen — die Rede. Besonders übersichtlich ist ein solches Diagramm, wenn sich die gezeichneten Linien nicht schneiden.

Firoz Kaderali, Werner Poguntke

3. Algorithmen

Zusammenfassung

Einen Baum erkennt man daran, daß er ein Graph ohne Kreise ist. Ist ein Diagramm eines Graphen vorgelegt, so wird man dies in der Regel durch wenige Blicke nachprüfen können. Es stellt sich nun aber die Frage, wie man einen Graphen am schnellsten auf seine Kreisfreiheit untersucht, der in einem Rechner (z. B. durch eine Inzidenzmatrix) abgespeichert ist. Es wäre sicher keine gute Methode, den Rechner ein Diagramm zeichnen zu lassen und dieses dann optisch zu inspizieren. Es geht also darum, ein günstiges Rechenverfahren, einen sogenannten Algorithmus, zur Lösung dieses Problems zu finden.

Firoz Kaderali, Werner Poguntke

4. Pseudodigraphen

Zusammenfassung

Ein Pseudodigraph (gerichteter Pseudograph) ist ein Tripel \( \overrightarrow P = (E,B,v) \) bestehend aus einer Eckenmenge E, einer Bogenmenge B und einer (Inzidenz-) Abbildung

$$ v:B \to E\; \times \;E $$

Firoz Kaderali, Werner Poguntke

5. Bewertungen

Zusammenfassung

Die Struktur von Pseudographen bzw. Pseudodigraphen wird reichhaltiger, wenn den Ecken, Kanten oder Bögen zusätzlich noch irgendwelche Zahlen zugeordnet werden, man spricht dann von Bewertungen. In den meisten Anwendungen von Pseudo(di)graphen hat man es mit bewerteten Strukturen zu tun, wobei die zugeordneten Zahlenwerte z. B. Verarbeitungszeiten von Teilaufgaben, Benutzungskosten von Leitungen oder deren Ausfallwahrscheinlichkeiten sein können usw.

Firoz Kaderali, Werner Poguntke

6. Kürzeste Wege und minimale Gerüste

Zusammenfassung

In vielen Anwendungen von Graphen fragt man nach besonders günstigen Wegen, oft handelt es sich dabei um möglichst kurze Wege. Die alltäglichsten Beispiele sind Straßennetze oder die Bus- und Bahnlinien eines Verkehrsverbundes, wo nach der kürzesten Möglichkeit gesucht wird, von einem Punkt zu einem anderen zu gelangen. Stehen auf einigen Teilstrecken verschiedene Verkehrsmittel zur Verfügung, so mag man auch nach der insgesamt billigsten Variante fragen. In einem Fernmeldenetz, wo die einzelnen Leitungen verschiedene Ausfallwahrscheinlichkeiten haben, ist die verlasslichste Route zwischen zwei Punkten von Interesse.

Firoz Kaderali, Werner Poguntke

7. Flüsse

Zusammenfassung

Bei der Untersuchung von Flüssen in Netzen geht es um die folgende Grundfrage: Wieviel kann von einer “Quelle” q zu einer “Senke” s transportiert werden, wenn obere Kapazitätsbeschränkungen für die einzelnen Verbindungen gegeben sind? Dabei werden wir im folgenden stets von einem Digraphen ausgehen, die Ergebnisse lassen sich in der Regel leicht auf den ungerichteten Fall übertragen. Ein Beispiel für einen Fluß in einem Netz haben wir bereits bei der Einführung von Bewertungen kennengelernt (vgl. 5.1.3). Es folgt nun die formale Definition.

Firoz Kaderali, Werner Poguntke

8. Wegeauswahl in Netzen

Zusammenfassung

Es geht in diesem Kapitel um das folgende Problem. Gegeben sei ein Kommunikationsnetz, in dem einzelne Systeme (oder “Stationen”) unter Nutzung von Verbindungsleitungen miteinander kommunizieren. Es muß geregelt werden, welche der Verbindungsleitungen genutzt werden sollen, wenn irgendwelche zwei Systeme miteinander in Kommunikation treten wollen.

Firoz Kaderali, Werner Poguntke

9. Zuverlässigkeit von Netzen

Zusammenfassung

Wir benutzen Graphen zur Modellierung der Struktur eines Kommunikationsnetzes. Ein Ziel ist es selbstverständlich, daß in dem Netz die Stationen möglichst zuverlässig miteinander kommunizieren können. Das Wort “zuverlässig” beziehen wir dabei nur auf die prinzipielle Kommunikationsfähigkeit (also Erreichbarkeit der Stationen) und nicht auf die Unversehrtheit bzw. Rekonstruierbarkeit der Nachrichteninhalte (Stichwort Fehlerkorrektur).

Firoz Kaderali, Werner Poguntke

10. Einige graphentheoretische Aspekte des VLSI-Layout

Zusammenfassung

Für die Implementierung logischer Funktionen mit mehreren Ausgängen haben sich Programmierbare Logikfelder als ein effektives Mittel erwiesen. Im Englischen spricht man von Programmable Logic Arrays — von dort wollen wir für das Weitere die Abkürzung PLA übernehmen.

Firoz Kaderali, Werner Poguntke

Backmatter