Mit einem Graphen kann man verschiedene Objekte und deren Beziehung untereinander darstellen. Die Galerie unten zeigt eine Menge unterschiedlicher Graphen, die aber alle grundlegende Gemeinsamkeiten haben.

Aufgabe:

1. Beschreibe, welche Gemeinsamkeiten alle in der Galerie dargestellten Graphen haben.
2. Versuche allgemein zu beschreiben, aus welchen Elementen ein Graph besteht.

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.

Um die Verbindungen der Knoten zu verwalten, wird eine Adjazenzmatrix verwendet. Funken ist die Adjazenzmatrix für das Haus vom Nikolaus dargestellt.

Eine 1 bedeutet, dass die beiden Knoten miteinander verbunden sind, eine 0, dass die beiden Kanten nicht miteinander verbunden sind.

Aufgabe 2: Stelle die Adjazenzmatrix für den folgenden Graphen auf:

1. Haus vom Nikolaus
   Im Projekt Haus vom Nikolaus lernst du den Umgang mit Graphen aus programmiertechnischer Sicht.
2. Soziale Netzwerke
   Im Projekt Soziale Netzwerke lernst du die Klassen Graph, Vertex und Edge kennen.
3. Graphen durchlaufen und in Graphen suchen
   Im Projekt Graphen durchlaufen lernst du die beiden Suchmethoden Tiefensuche und Breitensuche kennen.
4. Routing
   Im Projekt routing lernst du Algorithmen kennen, mit denen du den kürzesten Weg in einem Graphen ermitteln kannst.