Fachrat Informatik - Forum

Quoted

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.

Bei solch leichten Graphen sollte man es recht schnell an Gradfolge und Aufbau erkennen.

Hier liegt es schonmal nahe, sich die Graphen P4 und P5 näher anzuschauen. Mit ein wenig Nachdenken (oder auch einfach einem Blick auf das Blatt mit Isomorphietypen), erkennt man, dass es für die Gradfolge (22224) genau einen Isomorphietyp gibt, daher müssen P4 und P5 zwangsläufig isomorph sein.

Bleiben noch die vier Graphen mit gleicher Gradfolge (22233). Auch hier hilft zur Not ein Blick auf das besagte Blatt, um zu erkennen, dass sich die beiden möglichen Typen im Aufbau dahingehend unterscheiden, dass bei P1 und P3 die Knoten des Grades 3 direkt über eine Kante verbunden sind - bei P2 und P6 nicht.

Auch ein wenig Vorstellungskraft kann bei der Lösung recht hilfreich sein. Zieht man z.B. bei P6 den Knoten 5 unter die Knoten 2 und 3 und dreht dann den Graphen um 180°, so erhält man die Struktur von P2