Utente:Fabior1984/Sandbox-5

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

In teoria dei grafi l'algoritmo VF è un algoritmo di ricerca di sottostrutture in un grafo in grado di risolvere in maniera efficiente il problema dell'isomorfismo di grafi e sottografi. L'algoritmo è progettato per essere applicato su grafi di grandi dimensioni ed è basato sulla procedura con backtracking proposta da Ullman nel 1976.

L'algoritmo[modifica | modifica wikitesto]

L'algoritmo fornisce una soluzione più efficiente rispetto ad altri algoritmi per la ricerca delle sottostrutture in grafi. L'algoritmo è applicabile ad ogni tipo di grafo, è particolarmente adatto a grafi con etichette o attributi, utilizza una rappresentazione nello spazio degli stati con una strategia di ricerca depth-first (in profondità) ed ha cinque regole di fattibilità che permettono di ridurre lo spazio degli stati. Il matching tra due grafi e consiste nel determinare una mappatura che associa nodi di a nodi di e viceversa, tenendo conto di alcune costanti predefinite. Una mappatura è un insieme di coppie con e . Definiamo, inoltre, l'insieme , come un sottoinsieme di che identifica univocamente due sottografi di e , rispettivamente indicati come e tale da rappresentare il matching parziale dello stato ossia l'insieme corrente delle coppie di nodi dei due grafi che sono corrispondenti. Una transizione da uno stato ad uno stato successore consiste nell'aggiunta nello spazio degli stati di una coppia di nodi . Otteremo, dunque, un nuovo insieme con e . Per stabilire se una coppia da aggiungere allo stato produce uno stato inconsistente o meno si utilizza un'apposita funzione di fattibilità che ha lo scopo di filtrare più strade possibili per cercare di arrivare più velocemente alla soluzione. A tal scopo si costruisce un insieme delle coppie candidate. La scelta delle coppie da inserire in sfrutta i cosidetti terminal sets, indicati rispettivamente con e , che contengono i nodi direttamente connessi a quelli già inseriti nel mapping parziale e che provengono da e . Le coppie vengono scelte in modo da assicurare che l'eventuale inconsistenza venga riconosciuta quanto più velocemente possibile.

Prestazioni[modifica | modifica wikitesto]

Algoritmo VF2[modifica | modifica wikitesto]

Bibliografia[modifica | modifica wikitesto]