„Wurzel (Graphentheorie)“ – Versionsunterschied
| [gesichtete Version] | [gesichtete Version] |
Die letzte Textänderung von 93.221.184.63 wurde verworfen und die Version 145430685 von Ice Boy Tell wiederhergestellt. Das ist nur die Darstellung. |
erweitert von gerichteten Bäumen auf allgem. Graphen. |
||
| Zeile 1: | Zeile 1: | ||
Eine '''Wurzel''' ist in der [[Graphentheorie]] ein [[Knoten (Graphentheorie)|Knoten]] eines [[Graph (Graphentheorie)|Graphe]]<nowiki/>n, der besonders ausgezeichnet worden ist. Der Graph mit einer Wurzel wird als [[Wurzelgraph]] bezeichnet.<ref>{{Literatur |Autor=Peter Tittmann |Titel=Einführung in die Kombinatorik |Hrsg= |Sammelwerk= |Band= |Nummer= |Auflage= |Verlag= |Ort= |Datum=2014 |Seiten=210 |ISBN=978-3-642-54588-7 |DOI=10.1007/978-3-642-54589-4 |Online=http://link.springer.com/10.1007/978-3-642-54589-4 |Abruf=2018-05-10}}</ref> |
|||
| ⚫ | |||
| ⚫ | |||
Häufige Anwendungen finden Wurzeln bei der [[Traversierung]] von Graphen (bspw. mittels [[Breitensuche]] oder [[Tiefensuche]]). Die Wurzel stellt den Startknoten dar. Das Ergebnis der Graph-Traversierung ist ein [[Spannbaum]]. |
|||
| ⚫ | Bei [[Wurzelbaum|Wurzelbäumen]] ist die jeweilige Wurzel derjenige Knoten, von dem aus alle anderen Knoten im [[Baum (Graphentheorie)|Baum]] erreichbar sind und der selbst von keinem anderen Knoten aus erreichbar ist. Eine Wurzel ist somit der einzige Knoten in einem Baum, der keinen Vorgänger hat. Zeichnet man einen Baum, so ist die Wurzel immer der oberste Knoten des Baumes. Bäume haben in der [[Informatik]] immer genau eine Wurzel. Zerlegt man den ursprünglichen Baum in mehrere Teilbäume, so haben auch die entsprechenden Teilbäume wieder genau eine bestimmte Wurzel. Verallgemeinert man den Begriff der Wurzel auf allgemeine Graphen, so spricht man auch von [[Quelle_(Graphentheorie)|Quellen]]. |
||
== Definition == |
== Definition == |
||
| Zeile 8: | Zeile 13: | ||
== Beispiel == |
== Beispiel == |
||
| ⚫ | |||
* Die Wurzel des Beispielbaumes hat die Marke 1. |
* Die Wurzel des Beispielbaumes hat die Marke 1. |
||
* Die Wurzel des Teilbaumes, der aus den Knoten 5, 9 und 10 besteht, hat die Marke 5. |
* Die Wurzel des Teilbaumes, der aus den Knoten 5, 9 und 10 besteht, hat die Marke 5. |
||
* Die Wurzel des Teilbaumes, der nur aus dem Knoten 12 besteht, hat die Marke 12. |
* Die Wurzel des Teilbaumes, der nur aus dem Knoten 12 besteht, hat die Marke 12. |
||
== Einzelnachweisliste == |
|||
<br /> |
|||
[[Kategorie:Grundbegriff (Graphentheorie)]] |
[[Kategorie:Grundbegriff (Graphentheorie)]] |
||
Version vom 1. Februar 2020, 13:39 Uhr
Eine Wurzel ist in der Graphentheorie ein Knoten eines Graphen, der besonders ausgezeichnet worden ist. Der Graph mit einer Wurzel wird als Wurzelgraph bezeichnet.[1]
Häufige Anwendungen finden Wurzeln bei der Traversierung von Graphen (bspw. mittels Breitensuche oder Tiefensuche). Die Wurzel stellt den Startknoten dar. Das Ergebnis der Graph-Traversierung ist ein Spannbaum.
Bei Wurzelbäumen ist die jeweilige Wurzel derjenige Knoten, von dem aus alle anderen Knoten im Baum erreichbar sind und der selbst von keinem anderen Knoten aus erreichbar ist. Eine Wurzel ist somit der einzige Knoten in einem Baum, der keinen Vorgänger hat. Zeichnet man einen Baum, so ist die Wurzel immer der oberste Knoten des Baumes. Bäume haben in der Informatik immer genau eine Wurzel. Zerlegt man den ursprünglichen Baum in mehrere Teilbäume, so haben auch die entsprechenden Teilbäume wieder genau eine bestimmte Wurzel. Verallgemeinert man den Begriff der Wurzel auf allgemeine Graphen, so spricht man auch von Quellen.
Definition
Ein Knoten ist eine Wurzel genau dann, wenn gilt:
- Alle weiteren Knoten des Baumes sind von diesem Knoten aus erreichbar.
- Der Knoten hat keinen Vorgänger.
Beispiel
- Die Wurzel des Beispielbaumes hat die Marke 1.
- Die Wurzel des Teilbaumes, der aus den Knoten 5, 9 und 10 besteht, hat die Marke 5.
- Die Wurzel des Teilbaumes, der nur aus dem Knoten 12 besteht, hat die Marke 12.
Einzelnachweisliste
- ↑ Peter Tittmann: Einführung in die Kombinatorik. 2014, ISBN 978-3-642-54588-7, S. 210, doi:10.1007/978-3-642-54589-4 (springer.com [abgerufen am 10. Mai 2018]).