Graphentheorie

• Knoten (meist Zahlen)
• Kanten: Paare von Knoten (orientiert oder nicht)
• Weg: Folge von Knoten, die durch Kanten verbunden sind.
• Zusammenhängender Graph: Zwischen jedem Paar von Knoten existiert ein Weg
• Zyklus: Weg mit identischem Start- und Endknoten

• Zusammenhängender Graph ohne Zyklus.

Für Bäume beweisen Sie:

• Es gibt exakt einen Weg zwischen zwei beliebigen Knoten
• Ein Baum mit $n$ Knoten hat $n-1$ Kanten.

• Im einfachsten Fall ein Baum (keine Zyklen, garantierter Weg).
• Grundstuktur: Raster, Knoten sind ganzzahlige Koordinatenpunkte, Kanten achsenparallel, Länge 1.

Input Graph mit Knotenmenge $V$ und Kantenmengen $E$, Startknoten $s$, Zielknoten $z$.

Output Weg von $s$ nach $z$

1. Markiere alle Knoten mit None.
2. Setze Todo-Liste $t=(s)$
3. Solange $z$ mit None markiert ist, wiederhole:
   1. entferne einen Knoten $v$ aus $t$
   2. für alle Nachbarn $u$ von $v$, die noch mit None markiert sind:
      1. markiere $u$ mit $v$ (als Vorgäger)
      2. füge $u$ der Liste $t$ hinzu.
   3. Wenn $t$ leer ist, return “Kein Weg von $s$ zu $z$
4. Weg $w$ = $(z)$
5. Setze $v=z$
6. Solange $v \neq s$, wiederhole:
   1. Setze $v$ = Markierung von $v$
   2. Füge $v$ vorne zum Weg $w$ hinzu
7. return Weg $w$