Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenMittwoch, 19. Juni 2019 

Isomorphie von Graphen


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

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 1 =( V 1 E 1 ) und G 2 =( V 2 E 2 ) Graphen des selben Typs. Eine bijektive Abbildung p von V 1 nach V 2 heißt Isomorphie zwischen G 1 und G 2 falls gilt:

  • { v w } ist Kante von G 1 genau dann wenn { p ( v ) p ( w )} Kante von G 2 ist in ungerichteten Graphen ohne Mehrfachkanten
  • ( v w ) ist Kante von G 1 genau dann wenn ( p ( v ) p ( w )) Kante von G 2 ist in gerichteten Graphen ohne Mehrfachkanten
  • E 1 ({ v w })= E 2 ({ p ( v ) p ( w )}) in ungerichteten Graphen mit Mehrfachkanten
  • E 1 (( v w ))= E 2 (( p ( v ) p ( w ))) in gerichteten Graphen mit Mehrfachkanten
  • { v 1 ... v k } ist Kante von G 1 genau dann wenn { p ( v 1 ) ... p ( v k )} Kante von G 2 ist in Hypergraphen .
Zwei Graphen heißen zueinander isomorph falls es einen Isomorphismus zwischen ihnen Die Abbildung p heißt Automorphismus von G 1 bzw. G 2 falls zusätzlich G 1 = G 2 gilt.

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.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Isomorphe_Graphen.html">Isomorphie von Graphen </a>