Wurzelgraph

In der Graphentheorie ist ein Wurzelgraph oder gewurzelter Graph ${\displaystyle (G,o)}$ ein Graph ${\displaystyle G}$, in dem ein Knoten ${\displaystyle o}$ (die Wurzel) ausgezeichnet worden ist.^[1]

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

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

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