Kantenmenge

Kantenmenge bezeichnet in der Graphentheorie die Menge der Kanten eines Graphen. Ein Graph wird üblicherweise als Paar G = (V, E) beschrieben, wobei V die Menge der Knoten (Vertices) und E die Kantenmenge ist. Die Kantenmenge E enthält alle Verbindungen zwischen Knoten, deren Struktur der Graph bestimmt.

Für ungerichtete Graphen besteht E aus ungeordneten Paaren {u, v} von Knoten aus V, oft mit der Zusatzbedingung, dass u ≠ v (bei einfachen Graphen keine Schleifen). Für gerichtete Graphen (Digraphen) besteht E aus geordneten Tupeln (u, v) aus V × V; hier unterscheiden sich Eingangs- und Ausgangsverbindungen. In einfachen Graphen gibt es zudem in der Regel weder Schleifen (Kante von einem Knoten zu sich selbst) noch Mehrfachkanten zwischen denselben Knoten.

Wichtige Größen sind die Ordnung n = |V| und die Größe m = |E| des Graphen. Bezüglich der Verbindungen charakterisieren Maße wie der Grad eines Knotens (bei ungerichteten Graphen die Anzahl der an ihm angrenzenden Kanten; bei gerichteten Graphen In- und Out-Degree) die Struktur.

Kantenmenge lässt sich ändern, um neue Graphen zu modellieren: Kanten hinzufügen oder entfernen erzeugt verschiedene Teilgraphen oder Untergraphen. Eine kanteninduzierte Teilmenge E' ⊆ E definiert den entsprechenden Teilgraphen (mit V als Knotenbasis). Anwendungen finden sich in Netzwerktheorie, Pfad- und Flussproblemen sowie in vielen Modellierungen von Verbindungen.