Autor Tema: graph edit distance: python

0 Usuarios y 1 Visitante están viendo este tema.

11 Septiembre, 2016, 08:24 pm
Leído 1027 veces

johan.gonzalezp

  • Nuevo Usuario
  • Mensajes: 7
  • Karma: +0/-0
  • Sexo: Masculino
hola, tengo que programar graph edit distance en python
pero esto me ha llevado a otros problemas  que son:
1. igualdad entre grafos (yo se que dos grafos son iguales si existe un isomorfismo entre ellos, pero no puedo programar a la computadora
para que encuentre ese isomorfismo).
2.programar el máximo común sub-grafo (en el punto anterior e investigado que ese isomorfismo lo puedo encontrar con la matriz adyacente del grafo, y creo que el máximo común sub-grafo se debe trabajar con la matriz adyacente).
bueno, y eso es todo, agradezco cualquier ayuda, si tienen un libro que me proporcione más información en cuanto a la parte de programarlo se los agradezco. 
nota: los grafos no son dirigidos, por ende la matriz adyacente es simétrica.

12 Septiembre, 2016, 01:37 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 46,535
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

hola, tengo que programar graph edit distance en python
pero esto me ha llevado a otros problemas  que son:
1. igualdad entre grafos (yo se que dos grafos son iguales si existe un isomorfismo entre ellos, pero no puedo programar a la computadora
para que encuentre ese isomorfismo).

El problema de indentificar cuando dos grafos son isomorfos es complejo. Puedes leer algo sobre el asunto por aquí:

https://en.wikipedia.org/wiki/Graph_isomorphism_problem

Saludos.