El título lo dice todo. ¿Existe tal algoritmo? En términos más generales, ¿existe un algoritmo para decidir cuándo dos objetos son isomorfos en una categoría determinada?
Respuestas
¿Demasiados anuncios?
Keltia
Puntos
8104
El triángulo superior de un gráfico $G$ en $n$ vértices puede escribirse como una secuencia binaria de longitud $n(n-1)/2$ y, por tanto, como un número entero binario. A partir del $n!/|\mathrm{Aut}(G)|$ grafos distintos isomorfos a $G$ elige la que dé el menor número entero. Este es un invariante de la clase de isomorfismo, dos grafos son isomorfos si y sólo si dan lugar al mismo número entero.
Kurt
Puntos
1
Consulte el nuevo algoritmo de prueba de isomorfismo de grafos http://arxiv.org/abs/1004.1808
