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.
Aufbau eines Graphen
Ein Graph besteht aus Knoten (engl. Vertex). Knoten können mit Kanten (engl. 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 umgerichteten Graphen.