Wurzelgraph
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 (𝐺1, 𝑜1) und (𝐺2, 𝑜2) sind isomorph zueinander, wenn es einen Isomorphismus 𝐺1 → 𝐺2 gibt, der 𝑜1 auf 𝑜2 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.
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]).