12 – Erreichbarkeitsproblem

 

In einem System von Einbahnstraßen kann es sein, dass es nicht möglich ist, von Knoten vi aus den Knoten vj zu erreichen. Die Frage, ob es möglich ist (auf welchem Weg auch immer), nennt man “Erreichbarkeitsproblem”.

Im Folgenden wollen wir einen Algorithmus finden, der die Frage nach der Erreichbarkeit für jedes Paar (i, j) des Graphen beantwortet. Wir gehen dabei davon aus, dass der (gerichtete) Graph in einer Adjazenzmatrix gespeichert ist.

Beispiel:

Die zugehörige Matrix lautet:

A = \left( {\begin{array}{*{20}{c}}    {} & 1 & {} & {}  \\    {} & 1 & 1 & {}  \\    1 & {} & 1 & 1  \\    {} & {} & 1 & 1  \\   \end{array} } \right)

Um herauszufinden, welche Knoten man von einem bestimmten Knoten aus erreichen kann, erstellen wir einen Graphen, der jeweils den direkten Weg von vi nach j enthält.

Wir sehen leicht, dass in unserem Beispiel von jedem Knoten aus jeder andere in endlich vielen Schritten erreicht werden kann. Der Graph, der alle direkten Wege enthält, muss also eine Adjazenzmatrix ergeben, in der jedes Feld ungleich 0 ist.

Die Matrix A selbst enthält bereits die Wege der Länge 1. Wir sehen also schon, von welchem Knoten aus welcher andere Knoten direkt in einem Schritt erreichbar ist.
Um die Wege der Länge 2 zu dieser Matrix hinzuzufügen, multiplizieren wir A mit sich selbst:

A = \left( {\begin{array}{*{20}{c}}    1 & 1 &  &   \\     & 1 & 1 &   \\    1 &  & 1 & 1  \\     &  & 1 & 1  \\   \end{array} } \right),\quad \quad \quad A^2  = \left( {\begin{array}{*{20}{c}}    1 & 1 &  &   \\     & 1 & 1 &   \\    1 &  & 1 & 1  \\     &  & 1 & 1  \\   \end{array} } \right) \cdot \left( {\begin{array}{*{20}{c}}    1 & 1 &  &   \\     & 1 & 1 &   \\    1 &  & 1 & 1  \\     &  & 1 & 1  \\   \end{array} } \right) = \left( {\begin{array}{*{20}{c}}    1 & 2 & 1 &   \\    1 & 1 & 2 & 1  \\    2 & 1 & 2 & 2  \\    1 &  & 2 & 2  \\   \end{array} } \right)

Überall, wo der Eintrag in der Matrix nicht leer ist, gibt es einen Weg. Der Wert des Eintrags gibt allerdings keine Auskunft über die Länge des Weges, z.B. steht in A21,3 eine 1, obwohl der Weg von v1 nach v3 2 Schritte lang ist.

Wir sehen, dass noch nicht alle Plätze der Matrix belegt sind. Um auch die Wege hinzuzufügen, die in drei Schritten erreichbar sind, multiplizieren wir die Matrix A2 erneut mit A:

A^3  = A^2  \cdot A = \left( {\begin{array}{*{20}{c}}    1 & 2 & 1 &   \\    1 & 1 & 2 & 1  \\    2 & 1 & 2 & 2  \\    1 &  & 2 & 2  \\   \end{array} } \right) \cdot \left( {\begin{array}{*{20}{c}}    1 & 1 &  &   \\     & 1 & 1 &   \\    1 &  & 1 & 1  \\     &  & 1 & 1  \\   \end{array} } \right) = \left( {\begin{array}{*{20}{c}}    2 & 3 & 3 & 1  \\    3 & 2 & 4 & 3  \\    4 & 3 & 5 & 4  \\    3 & 1 & 4 & 4  \\   \end{array} } \right)

Nun sind alle direkten Wege gefunden. Den resultierenden Graphen nennt man transitive Hülle

In diesem Fall wurde die transitive Hülle im dritten Schritt gefunden, es sind also im ursprünglichen Graphen Wege mit der maximalen Länge von 3 vorhanden.
Allgemein ist die maximale Länge eines Weges in einem Graphen G mit der Knotenanzahl |V| nicht länger als |V|. Ein längerer Weg müsste ja einen der Knoten mehrmals benutzen und hätte somit eine verzichtbare “Schleife”.

Für den Rechenaufwand bedeutet dass, dass die Matrixmultiplikation im worst-case |V|-mal durchgeführt werden muss. Die Matrixmultiplikation selbst hat einen Rechenaufwand von O(|V|3). Dies liegt daran, dass das Matrixprodukt A·B=C komponentenweise berechnet wird, wobei für jedes festes Ci,j die Summe der Produkte von Zeilen- und Spalteneinträgen von A und B gebildet werden müssen.
Der gesamte Rechenaufwand dieses Verfahrens, um eine transitive Hülle zu finden, ist daher O(|V|4).

Besserer Algorithmus für die transitive Hülle

Hier die Java-Implementierung:

// Äußere Schleife:
for(int i = 0; i < iKnotenAnzahl; ++ i)
	// Innere Schleife:
	for(int j = 0; j < iKnotenAnzahl; ++ j)
		if(A[i][j] == 1)
			for(int k = 0; k < iKnotenAnzahl; ++ i)
				if(A[j][k] == 1)
					A[i][k] = 1;

Das sieht auf den ersten Blick ein wenig kompliziert aus und soll daher genauer erklärt werden. Für ein festes i durchläuft die innere Schleife alle Knoten und prüft, ob sie an den Knoten i angrenzen. Wenn ein Nachbarknoten j von i gefunden wurde, werden noch ein Mal alle Knoten durchlaufen. In diesem Durchlauf wird geprüft, welche Knoten k Nachfolger von j sind. Wenn k ein Nachfolger von j ist, und j ein Nachfolger von i, dann ist auch k ein Nachfolger von i (über zwei Kanten erreichbar). Daher wird die Verbindung von i nach k auf 1 gesetzt.
Dieser Prozess wird nun mit Hilfe der äußeren Schleife für jeden Knoten i durchgeführt. Dadurch, dass die Matrix schon beim ersten Durchlauf der äußeren Schleife geändert wird, arbeitet diese beim zweiten Durchlauf mit der geänderten Matrix weiter. Daher sind am Ende des äußeren Durchlaufes alle direkten Wege gefunden.

Der Rechenaufwand hierbei ist nur O(|V|3, da nur drei Schleifen ineinander verschachtelt sind. Die if-Abfragen verringern die Anzahl der Rechenoperationen weiter.

Der Algorithmus ist also besser als die Methode, die auf Matrixmultiplikation beruht. Die Funktion soll an einem Beispiel veranschaulicht werden:

Hier noch der Downloadlink zu dem Skript von Professor Holzer zu diesem Thema.

Ähnliche Artikel

Kommentar verfassen