Utente:Fabior1984/Sandbox-5

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

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 $G_{1}=(V_{1},E_{1})$ e $G_{2}=(V_{2},E_{2})$ consiste nel determinare una mappatura $M$ che associa nodi di $G_{1}$ a nodi di $G_{2}$ e viceversa, tenendo conto di alcune costanti predefinite. Una mappatura $M$ è un insieme di coppie $(n,m)$ con $n\in G_{1}$ e $m\in G_{2}$. Definiamo, inoltre, l'insieme $M(s)$, come un sottoinsieme di $M$ che identifica univocamente due sottografi di $G_{1}$ e $G_{2}$, rispettivamente indicati come $G_{1}(s)$ e $G_{2}(s)$ tale da rappresentare il matching parziale dello stato $s$ ossia l'insieme corrente delle coppie di nodi dei due grafi che sono corrispondenti. Una transizione da uno stato $s$ ad uno stato successore $s'$ consiste nell'aggiunta nello spazio degli stati di una coppia di nodi $(n,m)$. Otteremo, dunque, un nuovo insieme $M(s')=M(s)\cup (n,m)$ con $n\in V_{1}$ e $m\in V_{2}$. Per stabilire se una coppia $(n,m)$ da aggiungere allo stato $s$ produce uno stato inconsistente o meno si utilizza un'apposita funzione di fattibilità $F(s,n,m)$ che ha lo scopo di filtrare più strade possibili per cercare di arrivare più velocemente alla soluzione. A tal scopo si costruisce un insieme $P(s)$ delle coppie candidate. La scelta delle coppie da inserire in $P(s)$ sfrutta i cosidetti terminal sets, indicati rispettivamente con $T_{1}$ e $T_{2}$, che contengono i nodi direttamente connessi a quelli già inseriti nel mapping parziale e che provengono da $V_{1}$ e $V_{2}$. Le coppie vengono scelte in modo da assicurare che l'eventuale inconsistenza venga riconosciuta quanto più velocemente possibile.