In der Graphentheorie ist ein Wurzelgraph oder gewurzelter Graph ein Graph , in dem ein Knoten (die Wurzel) ausgezeichnet worden ist.[1]

Graph mit Knoten

Zwei Wurzelgraphen und sind isomorph zueinander, wenn es einen Isomorphismus gibt, der auf abbildet.

Beispiel: Im Bild rechts sind die Wurzelgraphen isomorph zueinander, aber nicht zu den anderen Wurzelgraphen. und sind ebenfalls isomorph zueinander. ist zu keinem der anderen Wurzelgraphen isomorph.

EinzelnachweisBearbeiten

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