Graphen und Bäume
Grafiken entnommen aus Saake, Sattler: "Algorithmen & Datenstrukturen"
Graphen
Gerichteter Graph
Als gerichteten Graph bezeichnet man einen Graph, der gerichtete Kanten enthält.
Ungerichteter Graph
Als ungerichteten Graph bezeichnet man einen Graph, der nur ungerichtete Kanten enthält. Dies schließt in der Regel auch Schleifen aus. Normalerweise gibt man den Zusatz ungerichtet nicht mit an, da man in der Regel meist nur ungerichteten Graphen meint, wenn man von Graphen spricht.
Gewichteter Graph
Als gewichteter Graph bezeichntet man einen Graph, der Knoten- oder Kantengewichte hat.
Planarer Graph
Ein planarer Graph (auch plättbarer Graph) ist ein Graph, der auf einer Ebene mit Punkten für die Knoten und Linien für die Kanten dargestellt werden kann, so dass sich die Kanten nur in den Knoten schneiden.
| Planarer Graph |
Kein planarer Graph |
 |
 |
Bipartiter Graph
Ein Graph heißt bipartit (auch paar), falls seine Knoten sich in zwei Teilmengen aufteilen lassen (Bipartition), so dass es zwischen den Knoten innerhalb einer Teilmenge keine Kanten gibt. Damit sind die Teilmengen stabile Mengen und die Bipartition impliziert eine mögliche 2-Färbung des Graphen. Umgekehrt sind alle 2-färbbaren Graphen bipartit.
Bäume
... weiter zu Bäume
Links
Merkblatt zu Graphen von Augustin (u.a. Adjazenzliste, Adjazenzmatrix, Dijkstra, Prim, Krustal, ...)