algorithm - siguientes - Editar distancia entre dos gráficos
distancia entre dos puntos perimetro (4)
Me pregunto si, al igual que para las cuerdas donde tenemos la distancia Levenshtein (o la distancia de edición) entre dos cuerdas, ¿hay algo similar para los gráficos?
Es decir, una medida escalar que identifica el número de operaciones atómicas (inserción / eliminación de nodos y bordes) para transformar un gráfico G1 en un gráfico G2 .
Creo que la distancia de edición de gráficos es la medida que estabas buscando.
La distancia de edición de gráficos mide el número mínimo de operaciones de edición de gráficos para transformar un gráfico a otro, y las operaciones de edición de gráficos permitidas incluyen:
- Insertar / eliminar un vértice aislado
- Insertar / eliminar un borde
- Cambiar la etiqueta de un vértice / borde (si se etiquetan gráficos)
Sin embargo, calcular la distancia de edición del gráfico entre dos gráficos es NP-hard. El algoritmo más eficiente para calcular esto es un algoritmo basado en A *, y existen otros algoritmos subóptimos.
Deberías mirar el documento Una encuesta de la distancia de edición de gráficos
Nota:
La distancia de Levenshtein (o la distancia de edición) se encuentra entre dos cadenas
Pero en Graph debes buscar al menos N! posición en la que se encuentra la Identidad de cada borde y vértice. Puede comparar fácilmente dos gráficos por índice único, pero la pregunta maestra es definir identidad para cada vértice y borde. Esta pregunta (encontrar la identidad para cada vértice y el borde en dos gráficos que pueden transformar) es muy difícil y se llamó isomorfismo problema (NP-Completo). Puede buscar sobre el gráfico de isomorfismo.
Para un gráfico general, es un problema NP completo como otros mencionaron en su respuesta. Pero para el árbol de gráficos hay algoritmos polinomiales bien conocidos. Puede ser el más famoso de ellos es el algoritmo "Zhang Shasha" que se publicó en 1989.