Ein Editor für Graphen

Auf dieser Seite werden die grundlegenden Begriffe erläutert, die im Zusammenhang mit Gravel verwendet werden. Der Schwerpunkt liegt hier auf den mathematischen Begriffen, um eine einheitliche Nomenklatur zu verwerden. Je nach Notwendigkeit kann das noch auf den Bereich Grafik (etwa Vektor- und Pixelgrafik), Graphenzeichnen und andere Layout-Begrifflichkeiten erweitert werden.

Mathematische Grundlagen

Definition 1.   Ein Graph G=(V,E) besteht aus einer Menge V von Knoten (Ecken, engl. vertices, nodes) und einer Menge E. Ein Knoten v ∈ V besitzt üblicherweise einen Index zur eindeutigen Identifikation. Eine Kante e ∈ E verbindet genau zwei Knoten. Mathematisch ist e=(u,v), wobei u,v ∈ V mit u≠v, die Kante verläuft von u nach v. u heißt dann Startknoten, v Endknoten der Kante.

Alternativ lässt sich ein Graph auch über die Adjazenzmatrix spezifizieren. Die Matrix ist vom Format |V|×|V| in der jedem Paar eine Anzahl Kanten zugeordnet wird, welche diese verbindet. In der Definition 1 entspricht dies entweder einer 0 falls eine Kante existiert, 0 sonst.

Zwei Knoten heißen adjazent, wenn sie durch eine Kante verbunden sind. Ein Knoten und eine Kante heißten inzident, wenn der Knoten Start- oder Endknoten der Kante ist.
Der Eingrad eines Knotens v ist die Anzahl Kanten, deren Endknoten v ist. Analog ist der Ausgrad die Anzahl Kanten, deren Startknoten v ist

Ein Graph heißt ungerichtet, wenn für jede Kante e=(u,v) ∈ E auch die Kante e=(v,u) ∈ E existiert. Dann lässt sich dies auch kurz schreiben als e={u,v}. Die Adjazenzmatrix eines ungerichteten Graphen ist symmetrisch und der Eingrad ist identisch mit dem Ausgrad eines Knotens

Weitere Variationen sind Schleifen, d.h. der Fall u=v wird in der Definition einer Kante erlaubt. In diesem Fall ist die Hauptdiagonale der Adjazenzmatrix eventuell mit Werten a_i,i ≠ 0 belegt.
Bei Mehrfachkanten wird die Menge E zu einer Multimenge, d.h. Kanten können mehrfach vorkommen. Dann besteht die Adjazenzmatrix nicht mehr ausschließlich aus Werten 0,1 sondern ein Eintrag zählt die Anzahl Kanten zwischen 2 Knoten.