Wichtiger Hinweis zum Inhalt des Online-LexikonsBei den auf dieser Seite aufgeführten Texten/Artikeln/Inhalten handelt es sich ausschließlich um fremde Inhalte, die sich die Aschendorff Verlag GmbH & Co. KG ausdrücklich nicht zu Eigen macht. Diese fremden Inhalte, die keiner regelmäßigen Überprüfung unterliegen, sind ausnahmslos solche der freien Enzyklopädie Wikipedia, für die keinerlei Verantwortung übernommen wird.

---

Lizenzbestimmungen Der Text/Artikel/Inhalt auf dieser Seite innerhalb der Rubrik "Online Lexikon" basiert, soweit nicht anders angegeben, auf dem Artikel Algorithmus von Hopcroft und Tarjan aus der freien Enzyklopädie Wikipedia. Die Inhalte stehen unter der GNU Lizenz für freie Dokumentation. Eine Liste der Autoren ist dort abrufbar.

Algorithmus von Hopcroft und Tarjan

Der Algorithmus von Hopcroft und Tarjan ist ein Algorithmus aus dem mathematischen_Teilgebiet der Graphentheorie. Mit ihm lässt sich in einem beliebigen zusammenhängenden ungerichteten_Graphen ohne Brücken eine Orientierung der Kanten finden, so dass der entstehende gerichtete_Graph stark_zusammenhängend ist. Der Name des Algorithmus geht auf die Computerwissenschaftler John E. Hopcroft und Robert Tarjan zurück.

Algorithmus

* Gegeben: zusammenhängender ungerichteter Graph $G\; =\; (V,E)$ ohne Brücken
* Gesucht: Orientierung $H$ von $G$, so dass $H$ stark zusammenhängend ist

Der Algorithmus von Hopcroft und Tarjan geht in zwei Schritten vor: Zuerst werden die Kanten eines Gerüstes orientiert, der über Tiefensuche bestimmt wird, anschließend werden die restlichen Kanten orientiert.

Es sei
* $M$ die Menge der markierten Knoten,
* $NM$ die Menge der nicht markierten Knoten,
* $m:V\; \backslash to\; \backslash mathbb\{N\}$ die Markierung der Knoten,
* $OM$ die Menge der Bögen, die durch die Orientierung der Kanten von $G$ entstanden sind.

1. Wähle einen beliebigen Knoten $x\; \backslash in\; V$ von $G$ aus, der markiert wird:
:Setze $m(x)\; =\; 1;\; M\; =\; \backslash \{x\backslash \};\; NM\; =\; V\; \backslash setminus\; \backslash \{x\backslash \};\; OM\; =\; \backslash emptyset$

2. Suche jetzt einen Knoten $y$ von $M$, der eine maximale Markierung $m(y)$ und gleichfalls adjazent zu einem Knoten $z$ aus $NM$ ist. Markiere jetzt $z$ mit $m(z)\; =\; m(y)+1$. Orientiere anschließend die Kante $\backslash \{y,z\backslash \}$ von $y$ zu $z$, so dass der Bogen $(y,z)$ entsteht.

Der markierte Knoten $z$ wird aus $NM$ entfernt und zu $M$ hinzugefügt, und der Bogen $(y,z)$ wird zu $OM$ hinzugefügt:
: $M\; =\; M\; \backslash cup\; \backslash \{z\backslash \};\; NM\; =\; NM\; \backslash setminus\; \backslash \{z\backslash \};\; OM\; =\; OM\; \backslash cup\; \backslash \{(y,z)\backslash \}$

Überprüfe, ob alle Knoten markiert wurden: Gilt $M\; \backslash neq\; V$, dann wiederhole Schritt 2.

3. Es gilt:
* Alle Knoten wurden markiert: $M\; =\; V$,
* ein Gerüst von $G$ ist orientiert.

Es lässt sich beweisen, dass alle Kanten, die jetzt noch keine Richtung haben, immer zwei Knoten mit unterschiedlicher Markierung verbinden. Jede nicht orientierte Kante $\backslash \{x,y\backslash \}$ mit $m(x)\; >\; m(y)$ wird nun von $x$ nach $y$ orientiert, d.h. vom Knoten mit der größeren zum Knoten mit der kleineren Markierung, und zu $OM$ hinzugefügt.

Die auf diese Weise konstruierte Orientierung $H\; =\; (V,OM)$ des Graphen $G$ ist stark zusammenhängend.

       VIDEO-NEWS UND ANGEBOTE