Selbstschleifen

Selbstschleifen bezeichnet in der Graphentheorie Kanten, die einen Knoten mit sich selbst verbinden. In ungerichteten Graphen handelt es sich um eine Schleife (v, v); in gerichteten Graphen um einen Pfeil vom Knoten zu sich selbst (v, v). Selbstschleifen treten häufiger in Multigraphen als in einfachen Graphen auf und modellieren oft reflexive oder selbstbezogene Beziehungen.

Mathematische Eigenschaften: Bei ungerichteten Graphen erhöht eine Selbstschleife den Knotengrad um 2. Bei gerichteten Graphen erhöht sie sowohl den Ein- als auch den Ausgangsgrad jeweils um 1. In der Adjazenzmatrix eines Graphen entspricht eine Selbstschleife einem Eintrag in der Diagonalen (aii ≠ 0). Selbstschleifen stellen einen Zyklus der Länge 1 dar; in vielen Algorithmen werden sie als spezieller, oft zu ignorierender Fall behandelt, können aber die Zyklenerkennung oder Gewichtungsmodelle beeinflussen.

Verwendung und Bedeutung: Selbstschleifen dienen der Modellierung reflexiver Relationen, zum Beispiel Selbstzugehörigkeiten oder Selbstbeziehungen in relationalen Modellen. Sie finden sich auch in Netzwerken, Datenstrukturen oder gewichteten Graphen, wo sie bestimmte Selbstverbindungen ausdrücken. In der Praxis hängt ihre Behandlung von der konkreten Problemstellung ab: Manche Modelle behandeln Schleifen als relevante Strukturen, andere ignorieren sie, um Vereinfachungen oder Comparisons zu erleichtern.

Beispiele und Folgen für die Praxis: Ein Graph mit einem Knoten A, der eine Schleife zu sich selbst besitzt, besitzt eine Zyklusstruktur der Länge 1. In Algorithmen für Pfadsuchen oder Zyklen können Selbstschleifen zu zusätzlichen Iterationen führen; in vielen Fällen lassen sie sich durch geeignete Vorverarbeitung entfernen, ohne die übergeordneten Ergebnisse zu verändern.

Siehe auch: Graphentheorie, Kante, Zyklus, Adjazenzmatrix, Knotengrad.