„Schleife (Graphentheorie)“ – Versionsunterschied
Zur Navigation springen
Zur Suche springen
| [gesichtete Version] | [gesichtete Version] |
Inhalt gelöscht Inhalt hinzugefügt
KKeine Bearbeitungszusammenfassung |
+ Belege für die Bezeichnungen |
||
| Zeile 1: | Zeile 1: | ||
[[Datei:6n-graph2.svg|miniatur|hochkant|Graph mit einer Schlinge in Knoten 1.]] |
[[Datei:6n-graph2.svg|miniatur|hochkant|Graph mit einer Schlinge in Knoten 1.]] |
||
Als '''Schleife''' oder '''Schlinge''' wird in der [[Graphentheorie]] eine [[Kante (Graphentheorie)|Kante]] bezeichnet, die einen [[Knoten (Graphentheorie)|Knoten]] mit sich selbst verbindet. Jede Schlinge bildet einen [[Zyklus (Graphentheorie)|Kreis]] der Länge eins in dem Graphen. |
Als '''Schleife''' oder '''Schlinge''' wird in der [[Graphentheorie]] eine [[Kante (Graphentheorie)|Kante]] bezeichnet, die einen [[Knoten (Graphentheorie)|Knoten]] mit sich selbst verbindet.<ref>{{Literatur |Hrsg=Guido Walz |Titel=Lexikon der Mathematik – Band 4 |Auflage=2 |Fundstelle=Stichwort ''Schlinge eines Graphen'' |Verlag=Springer |Datum=2017 |Seiten=463 |DOI=10.1007/978-3-662-53500-4 |ISBN=978-3-662-53500-4}}</ref><ref>{{Literatur |Autor=Lukas Pottmeyer |Titel=Diskrete Mathematik |Verlag=Springer |Datum=2019 |DOI=10.1007/978-3-662-59663-0_4 |ISBN=978-3-662-59662-3 |Seiten=78 |Kommentar=verwendet die Bezeichnung ''Schleife''}}</ref> Jede Schlinge bildet einen [[Zyklus (Graphentheorie)|Kreis]] der Länge eins in dem Graphen. |
||
Je nach Kontext können [[Graph (Graphentheorie)|Graphen]] so definiert werden, dass sie Schlingen zulassen oder ausschließen (oft in Verbindung mit der Zulassung von [[Mehrfachkante]]n): |
Je nach Kontext können [[Graph (Graphentheorie)|Graphen]] so definiert werden, dass sie Schlingen zulassen oder ausschließen (oft in Verbindung mit der Zulassung von [[Mehrfachkante]]n): |
||
| Zeile 12: | Zeile 12: | ||
Bei einem [[gerichteter Graph|gerichteten Graphen]] erhöht eine Schleife den [[Eingangsgrad|Eingangs-]] und den [[Ausgangsgrad]] eines Knotens jeweils um eins. Der inzidente Knoten einer Schleife ist also sowohl ihr Anfangs- als auch ihr Endknoten. |
Bei einem [[gerichteter Graph|gerichteten Graphen]] erhöht eine Schleife den [[Eingangsgrad|Eingangs-]] und den [[Ausgangsgrad]] eines Knotens jeweils um eins. Der inzidente Knoten einer Schleife ist also sowohl ihr Anfangs- als auch ihr Endknoten. |
||
== Einzelnachweise == |
|||
<references /> |
|||
[[Kategorie:Grundbegriff (Graphentheorie)]] |
[[Kategorie:Grundbegriff (Graphentheorie)]] |
||
Aktuelle Version vom 8. April 2023, 19:46 Uhr
Als Schleife oder Schlinge wird in der Graphentheorie eine Kante bezeichnet, die einen Knoten mit sich selbst verbindet.[1][2] 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
[Bearbeiten | Quelltext bearbeiten]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.
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ Guido Walz (Hrsg.): Lexikon der Mathematik – Band 4. 2. Auflage. Springer, 2017, ISBN 978-3-662-53500-4, S. 463, Stichwort Schlinge eines Graphen, doi:10.1007/978-3-662-53500-4.
- ↑ Lukas Pottmeyer: Diskrete Mathematik. Springer, 2019, ISBN 978-3-662-59662-3, S. 78, doi:10.1007/978-3-662-59663-0_4 (verwendet die Bezeichnung Schleife).