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.