Selbstschleife

Selbstschleife, englisch self-loop, bezeichnet in der Graphentheorie eine Kante, die von einem Knoten zu sich selbst führt. In gerichteten Graphen hat eine Selbstschleife die Form (v, v); in ungerichteten Graphen entspricht sie ebenfalls einer Verbindung des Knotens zu sich selbst. Selbstschleifen gehören nicht zu einfachen Graphen; Graphen, die keine Schleifen oder Mehrfachkanten zulassen, werden als einfache Graphen bezeichnet.

In gerichteten Graphen erhöhen Selbstschleifen den Ein- und den Ausgrad eines Knotens jeweils um 1. In ungerichteten Graphen erhöht eine Schleife den Knotengrad um 2, je nach verwendeter Konvention. In Adjazenzmatrizen erscheinen Selbstschleifen als Diagonalwerte ai,i (1 oder das zugehörige Gewicht). Selbstschleifen stellen auch Zyklen der Länge 1 dar und können deshalb bei Algorithmen zur Zykelerkennung berücksichtigt werden. In DFS-basierter Zykelerkennung gelten Selbstschleifen als zyklisch; bei Pfad- und Kürzestpfadalgorithmen sind sie meist zu vernachlässigen, es sei denn, sie tragen positive oder negative Kosten, die den Weg beeinflussen.

In Anwendungen tauchen Selbstschleifen häufig in Zustandsautomaten auf: Ein Zustand mit einer Schleifenüberführung bedeutet, dass derselbe Zustand bei bestimmten Eingaben verbleibt. In Netz- oder Regelungssystemen modellieren Schleifen Feedback oder Persistenz. Beispielhaft kann ein Graph mit einer Schleife von B nach B eine Selbstschleife darstellen; die Adjazenzmatrix enthält den entsprechenden Diagonalwert.