Datenstrukturen

Graphen


Ein Graph besteht aus Ecken und Kanten.

Eine Kante verbindet je zwei Ecken (=Knoten).
Wie viele Kanten von einer Ecke ausgehen und ob überhaupt welche von ihr ausgehen, hängt vom speziellen Graphentyp ab.
Es ist ebenso auch nicht gewährleistet, dass die Kanten in einer ebenen Darstellung einander nicht schneiden oder dass sie stets gradlinig zu zeichnen sind.
Auch Kanten unmittelbar von einer Ecke zu ihr selbst sind möglich.
--> etwas mathematischer formuliert

Fachbegriffe zu Graphen

ungerichtet

Ein Graph heißt ungerichtet, wenn K symmetrisch ist, also zu jeder Kante (a,b), das ist also eine von a zu b, auch die Kante (b,a), also die Verbindung von b zu a vorhanden ist.
--> etwas mathematischer formuliert

isolierte Ecken

Für die von uns betrachteten Graphen erheben wir die sinnvolle Forderung, dass es zu jeder Ecke a mindesten eine Kante von ihr weg oder zu ihr hin gibt. Das bedeutet: Es gibt keine isolierten Ecken.

endlich

Außerdem beschränken wir uns in der Regel auf endliche Graphen, also solche Graphen, bei denen die Zahl der Ecken und Kanten endlich ist, auch wenn ihre Zahl möglicherweise sehr groß ist.

Weg

Eine Folge von Ecken heißt Weg oder Pfad, wenn alle Ecken durch Kanten des Graphen verbunden sind.
--> etwas mathematischer formuliert

Länge dieses Weges

Bei einem Weg [a1 , a2 , a3 , ... , an] ist   n - 1   die Länge dieses Weges. Führt man allerdings eine Bewertungsfunktion für die Kanten ein, dann muss dieser Begriff Länge eines Weges noch verallgemeinert werden.

Nachfolger

Der Weg [a1 , a2 , a3 , ... , an , b] heißt Nachfolger des Weges, umgekehrt sprechen wir bei [ a1 , a2 , a3 , ... , an-1 ] vom Vorgänger.

Zyklus

Ein Weg, der dieselbe Ecke mehr als einmal enthält, heißt Zyklus oder Kreis, da man in diesem Fall auf einem Weg wiederholt zu dieser Ecke gelangen kann. Auch ein endlicher Graph kann also unendlich lange Wege enthalten.

zusammenhängend

Ein Graph, bei dem es zu je zwei verschiedenen Ecken a und b stets mindestens einen Weg von a nach b gibt, heißt zusammenhängend.

Baum

Ein zusammenhängender Graph ohne Zyklen heißt Baum.


Etwas(?) mathematischer formuliert :
Unter einem Graphen wird das Paar (E,K) aus einer Menge E von Ecken, die man auch als Knoten bezeichnet und einer Relation K in E verstanden, also einer Teilmenge von E x E. Die Elemente von K heißen Kanten.

Ein Graph heißt ungerichtet, wenn es zu jeder Kante (a,b) in K , auch die Kante (b,a)in K ist.

Eine Folge von Ecken [ a1 , a2 , a3 , a4 ... ] heißt Weg oder Pfad, wenn { ( a1 , a2 ) , ( a2 , a3 ) , ( a3 , a4 ) ... } eine Teilmenge von K ist.