Schleife (Graphentheorie)
Eine Schleife oder Schlinge bezeichnet in der Graphentheorie eine spezielle Kante, die einen Knoten mit sich selbst verbindet. Aus technischen Gründen ist diese formal immer eine gerichtete Kante. Das Vorhandensein, bzw. die Abwesenheit von Schleifen ist ein Klassifizierungsmerkmal von Graphen. Insbesondere spricht man von einem schleifenlosen oder schleifenfreien Graphen, wenn dieser keine Schleife enthält.
- Notation
-
- Darstellung
- ein Pfeil, der im Knoten a beginnt und dort auch wieder endet.
Schleife (a,a)
| Inhaltsverzeichnis |
Orientierung einer Schleife
Da Startknoten und Endknoten identisch sind, ist die Orientierung einer Schleife nicht variabel, so dass man eigentlich von einer ungerichteten Kante sprechen muss.
Mehrfachschleife
Sind einem Knoten eines Multigraphen mehrere Schleifen zugeordnet, so spricht man von einer Mehrfachschleife.
Topologische Graphentheorie
In der topologischen Graphentheorie ist eine Schleife eine Teilmenge eines topologischen Raums, die homöomorph zu einem Kreis ist und einen Knoten mit sich selbst verbindet.
Literatur
- William S. Massey: Algebraic topology, an introduction 4. Auflage. Springer, New York 1967, ISBN 0387902716