Beispiel Masse-Feder: Tarjan-Algorithmus

• Ausgangspunkt:
  • Gleichungen als bipartiter Graph
  • 2 Knotenmengen: Gleichungen und Variablen
  • Kante = Variable kommt in Gleichung vor
• Ziel:
  • numerierte Gleichungen
  • gefärbte Kanten
    • rot: Gleichung wird nach Variable aufgelöst
      ("steht links")
    • blau: Variable wird in Gleichung verwendet
      ("steht rechts")
• Verfahren:
  • suche Gleichungen mit genau einer ungefärbten Kante
    • Gleichung bekommt kleinste freie Nummer
    • Kante wird rot
    • andere Kanten der zugehörigen Variablen werden blau
  • suche Variablen mit genau einer ungefärbten Kante
    • zugehörige Gleichung bekommt größte freie Nummer
    • Kante wird rot
    • andere Kanten der zugehörigen Gleichung werden blau
  • iteriere, bis es nicht mehr weiter geht