Adjazenzstrukturen

Adjazenzstrukturen beschreiben die Verbindungen zwischen Elementen einer Menge, insbesondere die Nachbarschaftsbeziehungen in Graphen. Formal lässt sich eine Adjazenzrelation Adj ⊆ V×V zu einer endlichen Knotenmenge V definieren, wobei (u,v) ∈ Adj bedeutet, dass Knoten u und Knoten v benachbart sind. In einem ungerichteten, einfachen Graphen ist Adj symmetrisch und besitzt keine Schleifen; in gerichteten Graphen ist Adj im Allgemeinen nicht symmetrisch und erlaubt gerichtete Kanten.

Adjazenzstrukturen lassen sich auf verschiedene Weisen darstellen. Die gebräuchlichste Form ist die Adjazenzmatrix A, bei der A[i,j] = 1 gilt, wenn (i,j) ∈ Adj, ansonsten 0. Eine Adjazenzliste führt für jeden Knoten die benachbarten Knoten auf. In beiden Fällen codiert die Struktur die Nachbarschaft und damit die Kanten des Graphen.

Wichtige Eigenschaften betreffen Größenordnung und Verlauf von Wegen. Der Grad eines Knotens entspricht der Anzahl seiner Nachbarn; in gerichteten Graphen unterscheidet man Eingangsgrad und Ausgangsgrad. Graphen können zusammenhängend sein oder sich in Komponenten zerlegen. Die Adjazenzstruktur ermöglicht Algorithmik: DFS, BFS, kürzeste Pfade (Dijkstra, Floyd-Warshall), Transitive Hülle und Tests auf Zyklen oder Verbindungsbildung. Die Wahl der Repräsentation beeinflusst Speichernutzung und Laufzeit von Algorithmen, wobei Adjazenzlisten bei spärlichen Graphen oft effizienter sind als dichte Adjazenzmatrizen.

Anwendungen finden sich in Informatik, Netzwerktheorie, Sozialforschung, Verkehrs- und Molekülmodellierung. In jeder Domäne dient die Adjazenzstruktur dazu, Beziehungen zu analysieren, Muster zu erkennen und Operationen auf Nachbarn durchzuführen. Siehe auch Graph, Adjazenzmatrix, Adjazenzliste.