Graphentheorie:

Grundlegende Definition

Ein Graph besteht aus einer Menge an Knoten, benannt mit V, und einer Menge an Kanten, benannt mit E.

Graphen lassen sich unterteilen in…

Graphen mit maximal einer Kante zwischen zwei Knoten (ungerichtet)

Graphen mit einer Kante pro Richtung bei einem ungerichteten Graphen,

Graphen mit mehreren Kanten zwischen zwei Knoten (Multigraphen)

Graphen mit Kanten die über die adjazenten (benachbarte) Knoten hinausgehen (Hypergraphen) bezeichnet werden.

Formale Definition Ungerichteter Graph

Für einen ungerichteten Graphen ist die Menge der Kanten ( E ) definiert als eine Teilmenge der geordneten Knotenpaare x i und x j aus der Menge aller Knoten (V) eines Graphens.

Die Kantenmenge ist deshalb allgemein definiert als eine Teilmenge und keine echte Teilmenge, da es Graphen gibt, bei denen Knoten keinerlei Kantenverbindungen vorhanden sind.

Formale Definition Gerichteter Graph

Ein gerichteter Graph ist definiert durch seine Knotenmenge (V) und Kantenmenge (E), wobei die Kantenmenge E eine Teilmenge des kartesischen Produkts der Knotenmenge darstellt (V x V)

Die Definition der Kantenmenge E als Teilmenge des kartesischen Produkts der Knotenmenge V ist damit zu begründen, dass bei Bildung des kartesischen Produkts die Reihenfolge eine Rolle spielt und bei einem gerichteten Graph die Richtung der Kanten durch die Reihenfolge innerhalb der Knotenpaare eine Rolle spielt.

Erläuterung Definitionsunterschied (gerichtet vs ungerichtet)

	Knoten 1	Knoten 2
Knoten 1	Schlinge	Gerichtete Kante von Knoten 1 zu Knoten 2 {1,2}
Knoten 2	Gerichtete Kante von Knoten 2 zu Knoten 1 {2,1}	Schlinge

Die obige Tabelle bildet die Elementmenge des kartesischen Produkts eines Graphens mit 2 Knoten ab.

Da bei einem ungerichteten Graphen die Richtung spielt, ist die Kante von Knoten 1 zu Knoten 2 und die Kante von Knoten 2 zu Knoten 1 identisch.

Somit reicht es bei der formalen Definition aus, die Kantenmenge E als Teilmenge aller geordneten Knotenpaare zu definieren.

	Knoten 1	Knoten 2
Knoten 1	Schlinge	Gerichtete Kante von Knoten 1 zu Knoten 2 {1,2}
Knoten 2	Gerichtete Kante von Knoten 2 zu Knoten 1 {2,1}	Schlinge

Bei einem gerichteten Graphen ist dies nicht möglich, da sich die Elemente aus der Ergebnismenge des kartesischen Produktes der Knotenmenge durch ihre Richtung unterscheiden und somit nicht identisch bzw. äquivalent sind.