Kategorie

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 0      

isomorphie von graphen

ia ib ic id ie if ig ih ii ij ik il im
in io ip iq ir is it iu iv iw ix iy iz

Isomorphie von Graphen

Table of contents
1 Einleitung
2 Definitionen
3 Software

Einleitung

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.

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:

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!

Impressum

Datenschutzerklärung