Die Definitionen in der Graphentheorie variieren. Im Folgenden werden einige der grundlegenden Definitionen von Graphen und verwandten mathematischen Strukturen vorgestellt.
GraphEdit
Ein Graph (zur Unterscheidung von einem gerichteten Graphen manchmal auch ungerichteter Graph oder zur Unterscheidung von einem Multigraphen einfacher Graph genannt) ist ein Paar G = (V, E), wobei V eine Menge ist, deren Elemente Scheitelpunkte (Singular: Vertex) genannt werden, und E eine Menge von gepaarten Scheitelpunkten ist, deren Elemente Kanten (manchmal auch Glieder oder Linien) genannt werden.
Die Scheitelpunkte x und y einer Kante {x, y} nennt man die Endpunkte der Kante. Man sagt, dass die Kante x und y verbindet und auf x und y einfällt. Ein Scheitelpunkt kann zu keiner Kante gehören, in diesem Fall ist er mit keinem anderen Scheitelpunkt verbunden.
Ein Multigraph ist eine Verallgemeinerung, die es erlaubt, dass mehrere Kanten das gleiche Paar von Endpunkten haben. In manchen Texten werden Multigraphen einfach Graphen genannt.
Gelegentlich dürfen Graphen auch Schleifen enthalten, d. h. Kanten, die einen Knoten mit sich selbst verbinden. Um Schleifen zuzulassen, muss die obige Definition geändert werden, indem man Kanten als Multisets von zwei Scheitelpunkten statt als Zwei-Sets definiert. Solche verallgemeinerten Graphen werden Graphen mit Schleifen oder einfach Graphen genannt, wenn aus dem Kontext klar ist, dass Schleifen erlaubt sind.
Generell wird angenommen, dass die Menge der Scheitelpunkte V endlich ist; dies impliziert, dass die Menge der Kanten ebenfalls endlich ist. Unendliche Graphen werden manchmal betrachtet, werden aber eher als eine spezielle Art von binärer Relation angesehen, da die meisten Ergebnisse für endliche Graphen nicht auf den unendlichen Fall übertragbar sind oder einen etwas anderen Beweis benötigen.
Ein leerer Graph ist ein Graph, der eine leere Menge von Knoten (und damit eine leere Menge von Kanten) hat. Die Ordnung eines Graphen ist seine Anzahl der Scheitelpunkte |V|. Die Größe eines Graphen ist seine Anzahl der Kanten |E|. In manchen Zusammenhängen, z. B. zur Angabe der Rechenkomplexität von Algorithmen, ist die Größe jedoch |V| + |E| (andernfalls könnte ein nicht-leerer Graph die Größe 0 haben). Der Grad oder die Wertigkeit eines Knotens ist die Anzahl der Kanten, die zu ihm inzident sind; bei Graphen mit Schleifen wird eine Schleife doppelt gezählt.
In einem Graphen der Ordnung n ist der maximale Grad jedes Scheitelpunkts n – 1 (oder n, wenn Schleifen erlaubt sind), und die maximale Anzahl der Kanten ist n(n – 1)/2 (oder n(n + 1)/2, wenn Schleifen erlaubt sind).
Die Kanten eines Graphen definieren eine symmetrische Beziehung auf den Scheitelpunkten, die Adjazenzbeziehung genannt wird. Genauer gesagt, sind zwei Scheitelpunkte x und y benachbart, wenn {x, y} eine Kante ist. Ein Graph kann vollständig durch seine Adjazenzmatrix A spezifiziert werden, die eine n × n {\displaystyle n\times n} ist
quadratische Matrix, wobei Aij die Anzahl der Verbindungen von Knoten i zu Knoten j angibt. Für einen einfachen Graphen ist A i j ∈ { 0 , 1 } {\displaystyle A_{ij}\in \{0,1\}}
, was eine Unterbrechung bzw. Verbindung anzeigt, während A i i = 0 {\displaystyle A_{ii}=0}
(d.h., eine Kante kann nicht am selben Scheitelpunkt beginnen und enden). Graphen mit Selbstschleifen werden durch einige oder alle A i i {\displaystyle A_{ii}}
gleich einer positiven ganzen Zahl sind, und Multigraphen (mit mehreren Kanten zwischen Scheitelpunkten) werden durch einige oder alle A i j {\displaystyle A_{ij}}
gleich einer positiven ganzen Zahl sind. Ungerichtete Graphen haben eine symmetrische Adjazenzmatrix ( A i j = A j i {\displaystyle A_{ij}=A_{ji}}
).
Gerichteter GraphBearbeiten
Ein gerichteter Graph oder Digraph ist ein Graph, in dem die Kanten Orientierungen haben.
In einer eingeschränkten, aber sehr häufigen Bedeutung des Begriffs ist ein gerichteter Graph ein Paar G = ( V , E ) {\displaystyle G=(V,E)}
umfasst:
- V {\displaystyle V}
, eine Menge von Scheitelpunkten (auch Knoten oder Punkte genannt);
- E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 und x ≠ y } (x , y ) ∣ (x , y ) ∈ V 2 und x ≠ y }}
, eine Menge von Kanten (auch gerichtete Kanten, gerichtete Verbindungen, gerichtete Linien, Pfeile oder Bögen genannt), die geordnete Paare von Scheitelpunkten sind (d. h. eine Kante ist mit zwei verschiedenen Scheitelpunkten verbunden).
Um Mehrdeutigkeiten zu vermeiden, kann diese Art von Objekten genau als gerichteter einfacher Graph bezeichnet werden.
In der Kante ( x , y )
gerichtet von x {\displaystyle x}
nach y {\displaystyle y}
, die Scheitelpunkte x {\displaystyle x}
und y {\displaystyle y}
werden die Endpunkte der Kante genannt, x {\displaystyle x}
das Ende der Kante und y {\displaystyle y}
der Kopf der Kante. Die Kante soll x {\displaystyle x}
und y {\displaystyle y} verbinden
und auf x {\displaystyle x}
und auf y {\displaystyle y} einfallend sein
. Ein Vertex kann in einem Graphen existieren und nicht zu einer Kante gehören. Die Kante ( y , x ) {\displaystyle (y,x)}
nennt man die invertierte Kante von ( x , y ) {\displaystyle (x,y)}
. Mehrfache Kanten, die nach der obigen Definition nicht erlaubt sind, sind zwei oder mehr Kanten, die sowohl den gleichen Schwanz als auch den gleichen Kopf haben.
In einer allgemeineren Bedeutung des Begriffs, die mehrere Kanten zulässt, ist ein gerichteter Graph ein geordnetes Tripel G = ( V , E , ϕ ) {\displaystyle G=(V,E,\phi )}
umfasst:
- V {\displaystyle V}
, eine Menge von Scheitelpunkten (auch Knoten oder Punkte genannt);
- E {\displaystyle E}
, eine Menge von Kanten (auch gerichtete Kanten, gerichtete Verbindungen, gerichtete Linien, Pfeile oder Bögen genannt);
- ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 und x ≠ y } (x , y) in V^{2}}
, eine Inzidenzfunktion, die jede Kante auf ein geordnetes Paar von Scheitelpunkten abbildet (d.h. eine Kante ist mit zwei verschiedenen Scheitelpunkten verbunden).
Um Mehrdeutigkeiten zu vermeiden, kann man diese Art von Objekten genau als gerichtete Multigraphen bezeichnen.
Eine Schleife ist eine Kante, die einen Knoten mit sich selbst verbindet. Gerichtete Graphen, wie sie in den beiden obigen Definitionen definiert sind, können keine Schleifen haben, denn eine Schleife, die einen Knoten x {\displaystyle x}
mit sich selbst verbindet, ist die Kante (für einen gerichteten einfachen Graphen) oder fällt auf (für einen gerichteten Multigraphen) ( x , x ) {\displaystyle (x,x)}
die nicht in { ( x , y ) ∣ ( x , y ) ∈ V 2 und x ≠ y } {displaystyle \{(x,y)\mid (x,y)\in V^{2}\;{\textrm {und}}\;x\neq y\}}
. Um Schleifen zuzulassen, müssen die Definitionen also erweitert werden. Für gerichtete einfache Graphen ist die Definition von E {\displaystyle E}
in E ⊆ { ( x , y ) ∣ ( x , y ) ∈ V 2 } geändert werden. {\displaystyle E\subseteq \{(x,y)\mid (x,y)\in V^{2}\}
. Für gerichtete Multigraphen ist die Definition von ϕ {\displaystyle \phi }
sollte in ϕ : E → { ( x , y ) ∣ ( x , y ) ∈ V 2 } (x , y ) ∣ ( x , y ) ∈ V^{2}}
. Um Mehrdeutigkeiten zu vermeiden, können diese Arten von Objekten genau genommen ein gerichteter einfacher Graph, der Schleifen zulässt, und ein gerichteter Multigraph, der Schleifen zulässt (oder ein Köcher) genannt werden.
Die Kanten eines gerichteten einfachen Graphen, der Schleifen zulässt, G {\displaystyle G}
ist eine homogene Relation ~ auf den Eckpunkten von G {\displaystyle G}
, die man die Adjazenzrelation von G {\displaystyle G} nennt
. Genauer gesagt, für jede Kante ( x , y ) {\displaystyle (x,y)}
, ihre Endpunkte x {\displaystyle x}
und y {\displaystyle y}
sollen einander benachbart sein, was mit x {\displaystyle x}
~ y {\displaystyle y} bezeichnet wird
.
Gemischter GraphBearbeiten
Ein gemischter Graph ist ein Graph, in dem einige Kanten gerichtet und einige ungerichtet sein können. Er ist ein geordnetes Tripel G = (V, E, A) für einen gemischten einfachen Graphen und G = (V, E, A, ϕE, ϕA) für einen gemischten Multigraphen, wobei V, E (die ungerichteten Kanten), A (die gerichteten Kanten), ϕE und ϕA wie oben definiert sind. Gerichtete und ungerichtete Graphen sind Spezialfälle.
Gewichteter GraphBearbeiten
Ein gewichteter Graph oder ein Netzwerk ist ein Graph, in dem jeder Kante eine Zahl (das Gewicht) zugeordnet ist. Solche Gewichte können z. B. Kosten, Längen oder Kapazitäten repräsentieren, je nach Problemstellung. Solche Graphen treten in vielen Zusammenhängen auf, z. B. bei Kürzeste-Wege-Problemen wie dem Travelling-Salesman-Problem.