Un modo semplice per determinare se un dato grafico è sottografo di qualche altro grafico?

Question

Sto cercando un algoritmo per verificare se un dato grafico è sottografo di un altro dato grafico.

devo alcune condizioni per rendere questo NP completo po problema più fattibile ..

• I grafici hanno circa 20 < vertici.
• I grafici sono DAG.
• Tutti i vertici sono etichettati in modo non univoco ei vertici corrispondenti nel grafico principale e nel sottografo devono avere la stessa etichetta. Non so se sto usando le terminologie corrette (perché non ho seguito un corso di teoria dei grafi ...). Sarà qualcosa del tipo:

Il grafico a linee A - B è sottografo di A - B - A ma A - A non è un sottografo di A - B - A.

Qualsiasi suggerimento è a posto. Questa non è una domanda per i compiti a casa. : D

Answer 1

Se le etichette sono univoche, per un grafico di dimensioni N, esistono i bordi O(N^2), presupponendo che non vi siano loop automatici o bordi multipli tra ogni coppia di vertici. Usiamo E per il numero di bordi.

Se si eliminano i bordi impostati nel grafico padre, è possibile scorrere i bordi del sottografo, controllando se ognuno si trova nella tabella hash (e nella quantità corretta, se lo si desidera). Lo stai facendo una volta per ciascun lato, quindi O(E).

Chiamiamo il grafico G (con N vertici) e l'eventuale sottografo G_1 (con M vertici), e si desidera trovare G_1 is in G.

Dal momento che le etichette non sono univoci, è possibile, con la programmazione dinamica, costruire i sottoproblemi in quanto tali, invece - invece di avere O(2^N) sottoproblemi, uno per ogni sottografo, avete O(M 2^N) sottoproblemi - una per ogni vertice in G_1 (con M vertici) con ciascuno dei possibili sottografi.

G_1 is in G = isSubgraph(0, empty bitmask)

e gli stati sono impostati come tali:

isSubgraph(index, bitmask) = 
    for all vertex in G 
     if G[vertex] is not used (check bitmask) 
      and G[vertex]'s label is equal to G_1[index]'s label 
      and isSubgraph(index + 1, (add vertex to bitmask)) 
       return true 
    return false 

con il caso base essendo index = M, e si può verificare l'uguaglianza bordi, data la maschera di bit (e un'etichetta-implicito Mappatura). In alternativa, è anche possibile eseguire il controllo all'interno dell'istruzione if: è sufficiente controllare che, dato l'attuale index, il sottografo corrente G_1[0..index] sia uguale a G[bitmask] (con la stessa mappatura implicita dell'etichetta) prima di ricorrere.

Per N = 20, questo dovrebbe essere abbastanza veloce.

(aggiungi il tuo memo, oppure puoi riscriverlo utilizzando il tasto inferiore su DP).

Answer 2

OK, devo fare l'ovvia domanda. 1. Hai venti vertici. Cammina per ciascun grafico per primo, in ordine alfabetico tra i fratelli per ottenere stringhe. 2. Un grafico è un sottografo di un'altra iff una stringa è in un'altra.

Quindi, che altro si nasconde nelle specifiche del problema per rendere questo non possibile?

Answer 3

È possibile visualizzare questo come un problema di allineamento. Fondamentalmente si vuole creare una mappatura iniettiva a che associa ogni vertice in V_1 a un vertice in V_2. Una mappa allineamento un può essere segnata come segue:

s (a) = \ sum _ {(v, w) \ in E_1} \ sigma (v, w, a (v), una (w)) ,

dove \ sigma (v, w, a (v), una (w)) = 1, se (a (v), una (w)) \ in E_2 altrimenti è 0.

Penso che questo possa essere formulato sotto forma di un programma lineare intero.