Original von sommla
mal die
Lösung zu Aufgabenblatt 4 als Grundlage.
Bei Aufgabe 1 Teil b soll Isomorphismus zwischen den sechs Graphen bestimmt werden.
Gibt es ein Trick sowas schnell zu erkennen?
Bei dieser Frage ist die theoretische Informatik ausnahmsweise doch mal nützlich.
Kurz gesagt: Derzeit nicht bekannt, ob das
Isomorphieproblem für Graphen in der Komplexitätsklasse P liegt. Das bedeutet, daß es vermutlich keinen "schnellen" Algorithmus gibt, der für beliebige Paare von Graphen ermitteln kann, ob diese isomorph sind oder nicht. (Für bestimmte Spezialfälle ist dies aber möglich, siehe den obigen Link.)
Bei der konkreten Aufgabe könnte man jedoch so vorgehen, daß man sich anschaut, an wievielen Kanten jeder Knoten beteiligt ist. Wenn ich zum Beispiel die Graphen 1 und 3 vergleiche, ist klar, daß die Knotenmenge {1, 4} des Graphen 1 nur der Knotenmenge {3, 4} des Graphen 2 entsprechen kann. Mit ein wenig Herumprobieren läßt sich dann ein Isomorphismus finden oder begründen, warum keiner existiert. Der Vorteil dieser Methode ist, daß man durch diese Betrachtung der Kantenanzahlen bereits einen oder zwei "Startpunkte" für einen möglichen Isomorphismus hat.
Eine andere Möglichkeit wäre es, die Knoten des Graphen 1 so "im Kopf" zu verschieben, daß man den Graphen 3 erhält (oder andersrum). Hier könnte man in Graph 3 den Knoten zwei ein Stück nach links verschieben, so daß eine gedrehte Version von Graph 1 entsteht.