Einführung
| Begriff | Bedeutung |
|---|
| Vertex | Knoten |
| Grad eines Knotens | Anzahl anliegender Kanten |
| Graph G=(V,E) | mit Knotenmenge V und Kantenmenge E |
Spezielle Typen
| Begriff | Bedeutung |
|---|
| Weg (walk) | Folge benachbarter Knoten |
| Eulerweg | jede Kante genau einmal |
| Pfad (path) | Weg ohne wiederholte Knoten |
| Hamiltonpfad | jeder Knoten genau einmal |
| Zyklus (closed walk) | Weg mit Start = Ende, mindestens 2 Knoten (hin-zurück-hin), Endknoten inzident zu (verbunden mit) geraden Anzahl Kanten im Weg |
| Eulerzyklus | Eulerweg (jede Kante genau einmal) mit Anfang = Ende |
| Kreis (cycle) | Zyklus (Start = Ende) aber kein Knoten wird 2 mal besucht, also mindestens 3 Knoten |
- Wenn Eulerweg existiert, dann sind $\leq 2$ Knotengrade ungerade
- Laufzeit Eulerweg $O(n+m)$,
- Laufzeit Hamiltonpfad ist polynomiell unmöglich
- $\sum_{v∈V}\text{deg}(v)=2|E|$
- Weg ist Zyklus $\Longleftrightarrow$ der Endknoten vom Eulerweg ist inzident zu einer geraden Anzahl von Kanten
- Eulerzyklus existiert $\Longleftrightarrow$ alle Knotengerade
- Walk-Algorithmus:
walk(u):
if ∃v mit uv ∈ E, nicht markiert
markiere uv
walk(v)
- Euler-Walk Algorithmus nutzt eine
for Schleife statt einer if
Sprechweise
| Begriff | Bedeutung |
|---|
| adjazent | zwei Knoten sind benachbart |
| inzident | eine Kante ist anliegend zu einem Knoten |
| u erreicht v | gibt einen Weg zwischen u und v (Äquivalenzrelation) |
| Zusammenhangskomponente | Teil ist ineinander connected (Äquivalenzklasse der ÄR) |
Zusammenhang
| Begriff | Bedeutung |
|---|
| Graph zusammenhängend (connected) | gibt nur eine Zusammenhangskomponente, Graph ist nicht getrennt, (man kommt von jedem Knoten zu jedem anderen) |
| Baum (tree) | Graph ist zusammenhängend und hat keinen Kreis |
| cut vertex (Knoten) | entfernt man den Knoten und alle anliegenden Kanten ist der Graph disconnected |
| cut edge (Kante) | entfernt man die Kante (aber keine Knoten), ist der Graph disconnected |