prev up next

Previous: Map Up: skript Next: Implementation von Graphen

Graphen

Ein gerichteter Graph $G = (V,E) $ besteht aus Knotenmenge $V$ und Kantenmenge $E \subseteq V \times V$


Ein ungerichteter Graph $G = (V,E) $ besteht aus Knotenmenge $V$ und Kantenmenge $E \subseteq P_{2}(V)$
($P_{2}(V)$ sind alle 2-elementigen Teilmengen von $V$.)


Kanten können gewichtet sein durch eine Kostenfunktion $c: E \rightarrow \mathbb{R}$ .

Mit Graphen können binäre Beziehungen zwischen Objekten modelliert werden. Die Objekte werden durch die Knoten, die Beziehungen durch die Kanten modelliert.


Wir nennen eine Kante (x,y) inzident zum Knoten $x$ und zum Knoten $y$. Ein Weg ist eine Folge von adjazenten Knoten.
Ein Kreis ist ein Weg, der zurück zum Startknoten führt.



Unterabschnitte
prev up next
Previous: Map Up: skript Next: Implementation von Graphen