Graph/Bilder/Isomorphismus/1/Aufgabe/Kommentar

Wenn man einen Isomorphismus ${}\varphi \colon G\rightarrow G'$ von Graphen konstruieren möchte, sollte man im Allgemeinen die folgenden Invarianten (numerische Eigenschaften) berücksichtigen:

1. Knotengrad: für jeden Knotenpunkt ${}v$ von ${}G$ gilt ${}d(v)=d(\varphi (v))$. Ist ${}v$ insbesondere ein isolierter Punkt (bzw. Blatt, Punkt von minimalem/maximalem Grad), dann ist es ${}\varphi (v)$ auch.
2. Grad des Nachbarpunktes: Sei ${}\{v,w\}$ eine Kante von ${}G$. Wir nehmen an, dass ${}\varphi (v)$ bereits bestimmt wurde. Dann ist ${}\varphi (w)$ eine Nachbar von ${}\varphi (v)$ mit ${}d(\varphi (w))=d(w)$.
3. Untergraph: ist ${}v$ ein Knotenpunkt eines Untergraphen ${}H\subseteq G$, der eine Eigenschaft ${}P$ (z.B. regulär, vollständig, linear, ein Rundgang mit ${}n$ Knotenpunkten sein) besitzt, dann ist ${}\varphi (v)$ ein Knotenpunkt eines Untergraphen ${}H'\subseteq G'$, der auch die Eigenschaft ${}P$ besitzt.

In dieser Aufgabe hat jeder Knotenpunkt von beiden Graphen den Grad 3. Man sollte also nicht den Knotengrad berücksichtigen, sondern die Untergraphen. Um einen Isomorphismus zu konstruieren, kann man beispielsweise mit dem Rundgang mit 6 Knotenpunkten des linken Graphen beginnen.

Eine andere Möglichkeiten besteht darin, den einen Graphen in den anderen Graphen schrittweise zu „deformieren“. Man kann beispielsweise zuerst versuchen, den rechten Graphen ohne Überschneideung zu zeichnen, indem man die Kanten (denke an Fäden) umlegt. Dann erkennt man, dass es sich um isomorphe Graphen handelt.

Zur kommentierten Aufgabe