Wurzelgraph

In der Graphentheorie ist ein Wurzelgraph oder gewurzelter Graph $(G, o)$ ein Graph $G$ , in dem ein Knoten $o$ (die Wurzel) ausgezeichnet worden ist.

Zwei Wurzelgraphen $(G_{1}, o_{1})$ und $(G_{2}, o_{2})$ sind isomorph zueinander, wenn es einen Isomorphismus $G_{1} \to G_{2}$ gibt, der $o_{1}$ auf $o_{2}$ abbildet.

Beispiel: Im Bild rechts sind die Wurzelgraphen $(G, b), (G, c), (G, d), (G, e)$ isomorph zueinander, aber nicht zu den anderen Wurzelgraphen. $(G, a)$ und $(G, f)$ sind ebenfalls isomorph zueinander. $(G, g)$ ist zu keinem der anderen Wurzelgraphen isomorph.

Einzelnachweis

↑ 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]).

[1] 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]).