Isomorphie von Graphen
Table of contents |
2 Definitionen 3 Software |
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.
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:
Einleitung
Definitionen
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