Kennzeichen von Graphen

Ein Graph ist eine Datenstruktur, die aus Objekten und deren Verbindungen untereinander besteht.

Grundelemente

• Knoten: Elemente, von denen beliebig viele Knoten ausgehen mit eindeutigem Bezeichner, wobei die Lage des Knoten in der Graphendarstellung irrelevant ist, nur mit welchen anderen Knoten er durch Kanten verbunden ist.
• Kante: verbindet zwei Knoten eindeutig miteinander

Typen von Graphen

Ausgehend von der Struktur können verschiedene Typen von Graphen definiert werden

• zusammenhängender Graph: Man kann von jedem Knoten aus jeden anderen Knoten erreichen, notfalls über andere Knoten
• gewichteter Graph: die Kanten sind gewichtet, d.h. die Kanten bekommen unterschiedliche Prioritäten zugeordnet. Das kann eine Entfernungs oder Zeitangabe sein (z.B. bei Navigationssystemen) oder auch die Wichtigkeit des Weges sein.
• gerichteter Graph: manche oder alle Kanten sind nur in einer Richtung "begehbar". Somit muss beim Einfügen der Kante ein Startknoten und der Endknoten einer gerichteten Kante in der richtigen Reihenfolge angegeben werden. Die Kanten werden durch Pfeile ersetzt, bei beidseitiger Richtung werden zwei Pfeile eingezeichnet.
• vollständiger Graph: jeder Knoten hat zu jedem anderen Knoten eine Kante, d.h. man kann von jedem Knoten jeden anderen Knoten direkt, ohne über einen anderen Knoten gehen zu müssen, erreichen. Die Zahl der Kanten berechnet man wie folgt:

 $\frac{n*(n-1)}{2}$

Pfad/Weg

Pfad und Weg bezeichnen das selbe: den Weg von einem Knoten zu einem Zielknoten. Wenn der Startknoten mit dem Zielknoten identisch ist, spricht man von Zyklus (z.B. N/WÜ/HO/N), der zudem ein einfacher Pfad sein muss. Ein einfacher Pfad bezeichnet einen Weg ohne Abstecher, z.B. M/N/WÜ/F (Bild kommt noch). Bei diesem werden keine Knoten während des Weges doppelt besucht. Der Pfad M/N/WÜ/UL/S/WÜ/F ist dagegen kein einfacher Pfad.