Ungerichtet

Ungerichtet ist ein Begriff aus der Graphentheorie und bezeichnet einen Graphen, dessen Kanten keine Richtung haben. Zwischen zwei Knoten kann es höchstens eine Kante geben, die als ungerichtetes Paar {u, v} dargestellt wird. Im Gegensatz dazu steht der gerichtete Graph (Digraph), bei dem Kanten durch orientierte Paare (u, v) gekennzeichnet sind und eine Richtung besitzen.

Formal besteht ein ungerichteter Graph G aus einer Menge V von Knoten (Vertex) und einer Menge E von Kanten (Edges), wobei jede Kante als ungeordnetes Paar {u, v} von Knoten ausgedrückt wird. In einfachen ungerichteten Graphen gelten zusätzlich keine Schleifen (Kante von einem Knoten zu sich selbst) und keine Mehrfachkanten. In allgemeinen Graphen können Schleifen und Mehrfachkanten auftreten. Der Grad eines Knotens v, deg(v), entspricht der Anzahl der an ihn angrenzenden Kanten; bei Schleifen zählen diese Kanten in der Regel doppelt zum Grad.

Wichtige Eigenschaft ist die Symmetrie der Adjazenztmatrix: Die Adjazenzmatrix eines ungerichteten Graphen ist in der Regel symmetrisch. Adjazenzlisten haben ebenfalls eine natürliche, beidseitige Repräsentation, da Beziehungen ungerichtet sind. Konzepte wie Pfade, Kreise (Zyklen) und zusammenhängende Komponenten arbeiten unverändert im Vergleich zu gerichteten Graphen, Allerdings gelten Richtung und Orientierung nicht; Pfade verbinden Knoten durch aufeinander folgende, ungerichtete Kanten.

Typische Beispiele ungerichteter Graphen sind der vollständige Graph K_n, Wälder (Bäume), Zykelgraphen und Sterngrafen. Anwendungen finden sich in sozialen Netzwerken, Transport- und Kommunikationsnetzen sowie in chemischen Strukturen, wo Beziehungen oft ohne festgelegte Richtung dargestellt werden. Ungerichtete Graphen dienen zudem als Standardmodell für viele algorithmische Probleme, etwa zur Bestimmung von Wegen, zur Prüfung der Konnektivität oder zur Findung von Minimalbäumen.