Definitionen
Seien G1=(V1,E1) und G2=(V2,E2) Graphen des selben Typs. Eine bijektive Abbildung p von V1 nach V2 heißt Isomorphie zwischen G1 und G2, falls gilt:
- {v,w} ist Kante von G1 genau dann, wenn {p(v),p(w)} Kante von G2 ist in ungerichteten Graphen ohne Mehrfachkanten,
- (v,w) ist Kante von G1 genau dann, wenn (p(v),p(w)) Kante von G2 ist in gerichteten Graphen ohne Mehrfachkanten,
- E1({v,w})=E2({p(v),p(w)}) in ungerichteten Graphen mit Mehrfachkanten,
- E1((v,w))=E2((p(v),p(w))) in gerichteten Graphen mit Mehrfachkanten,
- {v1,...,vk} ist Kante von G1 genau dann, wenn {p(v1),...,p(vk)} Kante von G2 ist in Hypergraphen.
Zwei Graphen heißen zueinander isomorph, falls es einen Isomorphismus zwischen ihnen gibt. Die Abbildung p heißt Automorphismus von G1 bzw. G2, falls zusätzlich G1=G2 gilt.
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!