drei Graphen sollen auf Isomorphie untersucht werden.
Erstmal hab ich die Valenzsequenzen aufgestellt und einen Graphen (E3) dadurch ausgeschlossen.
Die beiden anderen Graphen haben
(4 3 2 2 2 2 2 1)
als Valenzsequenz.
Ich kann nirgends erlesen, wie man Graphen auf Isomorphie testet. Im Skript steht, dass es keinen effizienten Algorithmus gibt und das man es wohl durch aufzaehlen schafft. Ich haette das jetzt so gemacht:
Die Knoten mit Grad 4 muessen aufeinander uebertragen werden. Dann sieht man bereits, dass die Graphen nicht isomorph sein koennen, da der Knoten mit dem Grad 1 in Graph E1 direkt an dem Knoten mit Grad 4 haengt, in E2 allerdings nicht. Damit die Graphen isomorph sind muss gelten, dass
(v,w) genau dann Kante von E1 ist, wenn (p(v),p(w)) Kante in E2 ist. Die Punkte mit Grad 1 muessen jedoch aufeinander abgebildet werden, somit koennen die Graphen nicht isomorph sein.
Stimmt das? Wie geht ihr an solche Aufgaben heran?
Erstmal hab ich die Valenzsequenzen aufgestellt und einen Graphen (E3) dadurch ausgeschlossen.
Die beiden anderen Graphen haben
(4 3 2 2 2 2 2 1)
als Valenzsequenz.
Ich kann nirgends erlesen, wie man Graphen auf Isomorphie testet. Im Skript steht, dass es keinen effizienten Algorithmus gibt und das man es wohl durch aufzaehlen schafft. Ich haette das jetzt so gemacht:
Die Knoten mit Grad 4 muessen aufeinander uebertragen werden. Dann sieht man bereits, dass die Graphen nicht isomorph sein koennen, da der Knoten mit dem Grad 1 in Graph E1 direkt an dem Knoten mit Grad 4 haengt, in E2 allerdings nicht. Damit die Graphen isomorph sind muss gelten, dass
(v,w) genau dann Kante von E1 ist, wenn (p(v),p(w)) Kante in E2 ist. Die Punkte mit Grad 1 muessen jedoch aufeinander abgebildet werden, somit koennen die Graphen nicht isomorph sein.
Stimmt das? Wie geht ihr an solche Aufgaben heran?
