Hypergraph
Definition
Ein Hypergraph H ist ein Tupel (V, E), wobei V eine Menge von Knoten (oft auch Ecken genannt) und E eine Menge von Hyperkanten bezeichnet. Dabei ist E eine Teilmenge der Potenzmenge von V.
Einordnung
Spezialfälle von Hypergraphen sind schlichte Graphen, bei denen E eine Teilmenge der 2-elementigen Teilmengen von V ist.
Eine weitere Form von Graphen sind Multigraphen.
Hypergraphen mit gerichteten Kanten (gerichtete Hypergraphen) oder Mehrfachkanten (Multi-Hypergraphen) oder der Kombination aus beidem (gerichtete Multi-Hypergraphen) sind nur selten Gegenstand der Graphentheorie.
In der Regel betrachtet man nur endliche Hypergraphen, bei denen die Menge der Knoten endlich ist. Zwangsläufig ist dann auch die Menge der Kanten endlich. Hypergraphen mit unendlich vielen Knoten bezeichnet man als unendliche Hypergraphen. Normalerweise läßt man das Attribut "endlich" weg und kennzeichnet nur unendliche Multigraphen explizit.
Anschauung
Anschaulich ist ein Hypergraph nur schwer vor-/darstellbar. In der Regel zeichnet man eine Menge von Punkten, die den Knoten entsprechen, welche durch geschlossene Linien umkreist werden, die den Hyperkanten entsprechen.
Beispiel
Folgendes Bild zeigt einen Hypergraph.
Formal schreibt sich dieser wie folgt:
G = ({1,2,3,4,5,6,...???},{???})