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.

Graph $G$ mit Knoten $a,b,c,d,e,f,g$

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.