1142NK08 Aufgabe 5

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?

JoSeg schrieb:

Stimmt das? Wie geht ihr an solche Aufgaben heran?

Zum Vergrößern anklicken....

Hört sich gut an.
Ich habe dazu gelernt, dass man die Knotengrade vergleichen muss, und zwar auch immer die Knotengrade der direkten Nachbarn.

Hat also ein Knoten einen Grad 4 und einer seiner Nachbarn einen Grad 1, dann muss auch im anderen Graphen der Knoten mit Grad 4 einen solchen Nachbarn haben, sonst ist nix mit Isomorphie.

Das klingt gut. Ich überprüfe:
Wenn Valenzsequenz nicht angegeben ist:
Anzahl Knoten muss gleich sein
Valenzsequenz muss in beiden Graphen übereinstimmen
Sonst nur:
Graphen vergleichen: hat Knoten mit Grad x einen Nachbarknoten mit Grad y muss das im 2ten Graph auch so sein.

Laut Musterlösung einiger alter Klausuraufgaben passt das so.

okay, dann bin ich also nicht blind und hab den einfachen Algorithmus uebersehen, dann scheint das ab einem gewissen Punkt eher Ausprobieren zu sein und hoffen, dass es moeglichs eindeutige Knotengrade gibt.