¿Algún ejemplo de funcionamiento del algoritmo VF2?

Question

He estado leyendo VF2 algorithm para encontrar si dos gráficos son isomorfos, pero de alguna manera me falta el panorama general. Podría ser que me falta el trasfondo relevante en esta área, pero todo lo que veo es un conjunto de reglas que necesito usar en cada paso, sin ver una explicación intuitiva de por qué se están llevando a cabo los pasos.

De búsqueda básica en Google, parece que esto se considera uno de los algoritmos de facto para encontrar si dos gráficos son isomorfos, pero por alguna razón no puedo encontrar una explicación que sea lo suficientemente simple para entender a un nivel alto. ¿O es este algoritmo conocido por un nombre diferente?

En cualquier caso, ¿alguien sabe de algún ejemplo en ejecución de cómo funciona este algoritmo?

Answer 1

No estoy seguro de que sea eso lo que está buscando, pero el algoritmo de VF2 procede como se muestra a continuación.

Digamos que usted tiene 2 gráficos: V y V 'y que desea hacer coincidir V con V'

El algoritmo bajar un árbol, en cada paso se intenta hacer coincidir un elemento al lado de V con una de V 'y te paras cuando pasaste por todos los nodos en V' (cuando encuentras una hoja).

Algoritmo:

• Primer paso: coincidir V vacío con vacío gráfico V'.
• Segundo paso: tratar de matemáticas un nodo en V con un nodo en V '
• ...
• enésimo paso: tratar de coincidir con un nodo en V con un nuevo nodo en V', si no se puede retroceder un paso en el árbol y probar un nuevo partido en el paso anterior .. y si no puede volver de nuevo etc ...
• ...
• FIN: cuando se encuentra una hoja, es decir, cuando se pasó por todos los nodos en V 'o cuando recorrió el árbol completo sin encontrar una hoja.

Ejemplo

Aquí está un ejemplo, el algoritmo procede de izquierda a derecha del árbol.

"Un < -> B" significa Partido nodo A de V con el nodo B de V'

esperanza me queda claro y eso es lo que tu buscas.

Answer 2

He escrito un high-level overview of VF2, y también un bastante compacto from-scratch Java implementation for cheminformatics.