Wurzelgraph

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

Graph G {\displaystyle G} mit Knoten a , b , c , d , e , f , g {\displaystyle a,b,c,d,e,f,g}

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

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

Einzelnachweis

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