
Envoyé par
FrancisSourd
La notion de distance d'édition entre les chaînes se généralisent naturellement aux graphes. On parle souvent de "graph completion" ou "graph deletion" lorsqu'il s'agit d'ajouter ou supprimer des arêtes. J'imagine que des chercheurs ont généralisé cela lorsqu'on ajoute ou supprime des noeuds.
Il s'agit alors de trouver le coût minimal pour passer d'un graphe à l'autre ou, étant donné un graphe initial, de calculer le coût minimal pour obtenir un graphe ayant certaines propriétés (du genre "coloriable en 6 couleurs").
Partager