Dies ist eine alte Version des Dokuments!
Einführung
Mit einem Graphen kann man verschiedene Objekte und deren Beziehung untereinander darstellen. So zeigt der Graph rechts z.B. die Beziehung von Personen untereinander. Die Galerie zeigt eine Menge unterschiedlicher Graphen
- Beschreibe, welche Gemeinsamkeiten alle in der Galerie dargestellten Graphen haben.
- Versuche allgemein zu beschreiben, aus welchen Elementen ein Graph besteht.
Aufbau eines Graphens
Das Haus vom Nikolaus lässt sich auch als Graph interpretieren. Die fünf Ecken (Knoten) des Hauses werden mit Linien (Kanten) untereinander verbunden.
Beim Haus vom Nikolaus spielt es keine Rolle, ob die Linie z.B. von A nach B oder von B nach A gezeichnet wird. Man sagt, der Graph ist ungerichtet.
Man kann das Haus vom Nikolaus somit durch eine Menge V von Kanten (Vertex) und einer Menge E von Kanten (Edge) beschreiben: \begin{align*} V&=\{A,B,C,D,E\}\\ E&=\{(A,B),(A,C),(A,E),(B,C),(B,E),(C,D),(C,E),(D,E)\} \end{align*}
Die Kanten eines Graphens können mit einem Gewicht versehen werden. Repräsentieren die Knoten z.B. Orte, so kann das Kantengewicht für den Abstand dieser Orte stehen.
Aufbau eines Graphen
Ein Graph besteht aus Knoten (Vertex). Knoten können mit Kanten (Edge) untereinander verbunden sein.
Ein Kante kann zusätzlich noch eine Gewichtung (Zahl) besitzen.
Spielt bei einem Graphen die Richtung einer Kante keine Rolle, so spricht man von einem ungerichteten Graphen.