Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes
- 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, also grüne, Kante kreuzt. Wähle dann die kürzeste unter den unentschiedenen Kanten, die den Schnitt kreuzen und markiere diese grün.
- Die sogenannte Rote Regel: Wähle einen einfachen Zyklus, der keine verworfene (also rote) und mindestens eine ungefärbte Kante enthält. Verwirf die längste unter den unentschiedenen Kanten im Zyklus (also markiere diese rot).
Solange einer dieser beiden Regeln anwendbar ist, soll er fortgeführt werden. Dieser Algorithmus ist nichtdeterministisch.
Siehe auch
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 — In der Graphentheorie werden unterschiedliche Algorithmen nach Robert Tarjan benannt: Der Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten Der Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes Der Algorithmus … 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
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
Liste von Algorithmen — Dies ist eine Liste von Artikeln zu Algorithmen in der deutschsprachigen Wikipedia. Siehe auch unter Datenstruktur für eine Liste von Datenstrukturen. Inhaltsverzeichnis 1 Klassen von Algorithmen nach Komplexität 2 Klassen von Algorithmen nach… … Deutsch Wikipedia
