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 Informatiker 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, das ü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 \to \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 \in V von G aus, der markiert wird:

Setze m(x) = 1; M = \{x\}; NM = V \setminus \{x\}; OM = \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 {y,z} 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 \cup \{z\}; NM = NM \setminus \{z\}; OM = OM \cup \{(y,z)\}

Überprüfe, ob alle Knoten markiert wurden: Gilt M \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 {x,y} 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.


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten — Der Algorithmus von Tarjan (nach seinem Erfinder Robert Tarjan) dient in der Graphentheorie zur Bestimmung der starken Zusammenhangskomponenten (SZKn) eines Graphen. Inhaltsverzeichnis 1 Idee 2 Die Wurzeleigenschaft 3 Der Algorithmus in… …   Deutsch Wikipedia

  • Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes — Der Algorithmus von Tarjan wird in der Graphentheorie benutzt, um minimale Spannbäume zu bestimmen. Für die Kantenauswahl nach Robert Tarjan gibt es zwei Markierungsregeln: Die sogenannte Grüne Regel: Erzeuge einen Schnitt, der keine gewählte,… …   Deutsch Wikipedia

  • Hopcroft — John Edward Hopcroft (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker. Biographie 1961 machte Hopcroft seinen ersten Abschluss als Bachelor an der Universität von Seattle, danach wechselte er an die Stanford University und… …   Deutsch Wikipedia

  • Robert Endre Tarjan — (* 30. April 1948 in Pomona, Kalifornien) ist ein US amerikanischer Informatiker. 1986 wurde er zusammen mit John E. Hopcroft für das Design und die Analyse von Algorithmen und Datenstrukturen mit dem Turing Award ausgezeichnet. Er ist Professor… …   Deutsch Wikipedia

  • John E. Hopcroft — John E. Hopcroft, 2009 John Edward Hopcroft (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker. 1986 wurde er zusammen mit Robert Tarjan für das Design und die Analyse von Algorithmen und Datenstrukturen mit dem Turing Award… …   Deutsch Wikipedia

  • John Edward Hopcroft — (* 7. Oktober 1939 in Seattle) ist ein amerikanischer Informatiker. Biographie 1961 machte Hopcroft seinen ersten Abschluss als Bachelor an der Universität von Seattle, danach wechselte er an die Stanford University und erlangte dort 1962 den… …   Deutsch Wikipedia

  • Robert Tarjan — 2010 Robert „Bob“ Endre Tarjan (* 30. April 1948 in Pomona, Kalifornien) ist ein amerikanischer Informatiker. 1986 wurde er zusammen mit John E. Hopcroft für das Design und die Analyse von Algorithmen und Datenstrukturen mit dem Turing Award… …   Deutsch Wikipedia

  • Turing-Award — Der nach Alan Turing benannte und mit 250.000 US Dollar dotierte Turing Award (offizielle Bezeichnung: A. M. Turing Award) wird jährlich von der Association for Computing Machinery (ACM) an Personen verliehen, die sich besonders um die… …   Deutsch Wikipedia

  • Turing-Preis — Der nach Alan Turing benannte und mit 250.000 US Dollar dotierte Turing Award (offizielle Bezeichnung: A. M. Turing Award) wird jährlich von der Association for Computing Machinery (ACM) an Personen verliehen, die sich besonders um die… …   Deutsch Wikipedia

  • Turingpreis — Der nach Alan Turing benannte und mit 250.000 US Dollar dotierte Turing Award (offizielle Bezeichnung: A. M. Turing Award) wird jährlich von der Association for Computing Machinery (ACM) an Personen verliehen, die sich besonders um die… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”