Modifier la distance entre deux graphiques

Question

Je me demandais si, comme pour les cordes où nous avons la distance de Levenshtein (ou modifier la distance) entre deux cordes, y a-t-il quelque chose de similaire pour les graphes?

Je veux dire, une mesure scalaire qui identifie le nombre d'opérations atomiques (insertion/suppression de nœuds et de bords) pour transformer un graphique G1 en un graphique G2.

Answer 1

Note:

La distance Levenshtein (ou la distance d'édition) est entre deux chaînes

Mais dans le graphique, vous devriez chercher entre au moins N! position que vous trouvez l'identité de chaque bord et sommet. Vous pouvez facilement comparer deux graphiques par index unique, mais La question maîtresse est de définir une identité pour chaque sommet et chaque arête. Cette question (trouver l'identité de chaque sommet et arête dans deux graphiques qu'ils peuvent transformer) est très difficile et était appelé problème d'isomorphisme (NP-Complete). Vous pouvez rechercher sur le graphique d'isomorphisme.

Answer 2

Pour un graphe général, c'est un problème NP-complet comme d'autres mentionné dans leur réponse. Mais pour l'arbre, il existe des algorithmes polynomiaux bien connus. Peut-être le plus célèbre d'entre eux est "Zhang Shasha" algorithme qui a été publié en 1989.

Answer 3

Je pense que la distance d'édition graphique est la mesure que vous cherchiez.

mesures de distance Graphique de modifier le nombre minimum d'opérations d'édition graphique pour transformer un graphique à l'autre, et les opérations d'édition graphique permis comprend:

• Insérer/supprimer un sommet isolé
• Insérer/supprimer un bord
• modifier l'étiquette d'un sommet/bord (si les graphiques marqués)

Cependant, le calcul de la distance d'édition graphique entre deux graphes est NP-dur. L'algorithme le plus efficace pour calculer ceci est un algorithme basé sur A *, et il existe d'autres algorithmes sous-optimaux.

Answer 4

Vous devriez regarder le papier A survey of graph edit distance