Isomorphie von Graphen

aus Wikipedia, der freien Enzyklopädie

Bei der Untersuchung graphentheoretischer Probleme kommt es meist nur auf die Struktur der Graphen, nicht aber auf die Bezeichnung ihrer Knoten an. In den allermeisten Fällen sind die untersuchten Grapheneigenschaften dann invariant bzgl. Isomorphie, die im folgenden genauer definiert wird.

[Bearbeiten] Definitionen

Seien G₁=(V₁,E₁) und G₂=(V₂,E₂) Graphen des selben Typs. Eine bijektive Abbildung p von V₁ nach V₂ heißt Isomorphismus zwischen G₁ und G₂, falls gilt:

• {v,w} ist Kante von G₁ genau dann, wenn {p(v),p(w)} Kante von G₂ ist in ungerichteten Graphen ohne Mehrfachkanten,
• (v,w) ist Kante von G₁ genau dann, wenn (p(v),p(w)) Kante von G₂ ist in gerichteten Graphen ohne Mehrfachkanten,
• E₁({v,w})=E₂({p(v),p(w)}) in ungerichteten Graphen mit Mehrfachkanten,
• E₁((v,w))=E₂((p(v),p(w))) in gerichteten Graphen mit Mehrfachkanten,
• {v₁,...,v_k} ist Kante von G₁ genau dann, wenn {p(v₁),...,p(v_k)} Kante von G₂ ist in Hypergraphen.

Zwei Graphen heißen zueinander isomorph, falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung p heißt Automorphismus von G₁ bzw. G₂, falls zusätzlich G₁=G₂ gilt.

[Bearbeiten] Software

• http://cs.anu.edu.au/people/bdm/nauty/ - nauty, ein Programm zur Berechnung der Automorphismengruppen und der kanonischen Labelings von Graphen. Zwei Graphen sind genau dann isomorph, wenn ihre kanonischen Labelings übereinstimmen.