Isomorphie von Graphen

Einleitung

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

Definitionen

Seien G ₁ =( V ₁ E ₁ ) und G ₂ =( V ₂ E ₂ ) Graphen des selben Typs. Eine bijektive Abbildung p von V ₁ nach V ₂ heißt Isomorphie 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 .

Software

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

Bücher zum Thema Isomorphie von Graphen

Dieser Artikel von Wikipedia unterliegt der GNU FDL.