4.3.6. Otros problemas con grafos.
Comparación de grafos: Dados dos grafos G=(Vg, Ag) y F=(VF, AF), determinar si son iguales o no.
La comparación se puede realizar fácilmente, comprobando si se cumple que Vg= VF y Ag= AF.
Isomorfismo de grafos: Dos grafos G=(Vg, Ag) y F=(VF, AF) se dice que son isomorfos si existe una asignación de los nodos de Vg con los nodos de VF tal que se respetan las aristas.
- El isomorfismo de grafos es también un problema NP-completo, la solución consistiría básicamente en comprobar todas las posibles asignaciones.