Isomorfismo de grafos

Dos grafos $G_1=(V_1,E_1)$ y $G_2=(V_2,E_2)$ se dicen que son isomorfos si existe una biyección (a la que llamamos, isomorfismo) $f:V_1\to V_2$ tal que

$$\{u,v\}\in E_1\iff \{f(u),f(v)\}\in E_2,$$

para todo $u,v\in V_1$.

El número de grafos no isomorfos crece exponencialmente con el número $N$ de vértices.¹

Footnotes

1. Hein et. al. Entanglement in Graph States and its Applications ↩