Schleife (Graphentheorie)
Als Schleife oder Schlinge wird in der Graphentheorie eine Kante bezeichnet, die einen Knoten mit sich selbst verbindet. Jede Schlinge bildet einen Kreis der Länge eins in dem Graphen.
Je nach Kontext können Graphen so definiert werden, dass sie Schlingen zulassen oder ausschließen (oft in Verbindung mit der Zulassung von Mehrfachkanten):
- Lässt man Schleifen oder Mehrfachkanten in der Definition von Graphen zu, wird ein Graph ohne Schleifen und Mehrfachkanten zur Unterscheidung als Einfacher Graph bezeichnet. Ein Graph ohne Schleifen wird schleifenloser, schleifenfreier oder schlingenfreier Graph genannt.
- Schließt man Schleifen und Mehrfachkanten in der Definition von Graphen aus, wird ein Graph mit Schleifen oder Mehrfachkanten zur Unterscheidung als Multigraph bezeichnet.
Knotengrad
Bei einem ungerichteten Graphen ist der Grad eines Knotens gleich der Anzahl seiner Nachbarknoten. Die Schleife ist ein Spezialfall, da sie den Grad eines Knotens um zwei erhöht. Der (einzige) inzidente Knoten einer Schleife wird also zweimal als sein eigener Nachbar gezählt.
Bei einem gerichteten Graphen erhöht eine Schleife den Eingangs- und den Ausgangsgrad eines Knotens jeweils um eins. Der inzidente Knoten einer Schleife ist also sowohl ihr Anfangs- als auch ihr Endknoten.