Modifica la distanza tra due grafici

Question

Mi chiedo se, come per le stringhe in cui abbiamo la distanza di Levenshtein (o modifica la distanza) tra due stringhe, c'è qualcosa di simile per i grafici?

Intendo, una misura scalare che identifica il numero di operazioni atomiche (inserimento e cancellazione di nodi e bordi) per trasformare un grafico G1 in un grafico G2.

Answer 1

Nota:

La distanza Levenshtein (o modificare la distanza) è tra due stringhe

Ma nel grafico occorre eseguire la ricerca tra almeno N! posizione che trovi Identità di ogni spigolo e vertice. È possibile confrontare facilmente tra due grafici per indice univoco, ma La domanda principale è definire l'identità per ogni vertice e bordo.questa domanda (trovare l'identità per ogni vertice e spigolo in due grafici che possono trasformare) è molto difficile ed è stata chiamato problema di isomorfismo (NP-Complete). È possibile cercare informazioni sul grafico dell'isomorfismo.

Answer 2

Per un grafico generale è un problema NP-completo come altri menzionati nella risposta. Ma per il grafico ad albero sono noti algoritmi polinomiali. Può essere più famoso di loro è l'algoritmo "Zhang Shasha" che è stato pubblicato nel 1989.

Answer 3

Penso che la distanza di modifica del grafico è la misura che stavi cercando.

Grafico modifica misure di distanza il numero minimo di operazioni grafico di modifica per trasformare un grafico ad un altro, e le consentiti operazioni grafico modifica comprende:

• inserire/eliminare un vertice isolato
• Inserimento/cancellazione di un bordo
• Modificare l'etichetta di un vertice/bordo (grafici se etichettati)

Tuttavia, calcolando la distanza del grafico di montaggio tra due grafici è NP-hard. L'algoritmo più efficiente per calcolare questo è un algoritmo basato su A *, e ci sono altri algoritmi sub-ottimali.

Answer 4

Si dovrebbe guardare la carta A survey of graph edit distance