Isomorphien

Def: Abbildung h : V(G)$\to$V(H) heißt Isomorphie zwischen Graphen G und H, falls

• h ist bijektiv (umkehrbar eindeutig)
• $\forall$x, y $\in$ V(G) : xy $\in$ E(G)$\iff$h(x)h(y) $\in$ E(H)

Def: Graph G ist isomorph zu Graph H, Schreibweise G $\cong$ H, falls Isomorphie h zwischen G und H existiert.

Wir schreiben oft = statt $\cong$.

Bemerkung: Graph-Isomorphie ist offensichtlich in NP (ein behauptetes h läßt sich schnell testen), aber es ist unklar, ob es in co-NP ist. (gibt es einen einfachen Beweis für Nicht-Isomorphie?)