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

Question

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

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

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

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

Tutti i suggerimenti sono bene. Questa non è una questione compiti a casa btw. : D

Answer 1

Se le etichette sono uniche per un grafico della dimensione N, ci sono dei bordi O(N^2), assumendo non ci sono cicli autonomi o più spigoli tra ogni coppia di vertici. uso E di Let per il numero di spigoli.

Se hash i bordi impostati nel grafico genitore, si può passare attraverso i bordi della sottografo, controllando se ognuno è nella tabella hash (e nella giusta quantità, se lo si desidera). Lo stai facendo una volta per ogni bordo, di conseguenza, O(E).

chiamata di lasciare che il G grafico (con vertici N) e l'eventuale G_1 sottografo (con vertici M), 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 sottoproblemi O(2^N), uno per ogni sottografo, avete sottoproblemi O(M 2^N) - una per ogni vertice in G_1 (con vertici M ) con ciascuno dei possibili sottografi.

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

e gli stati sono impostati come ad esempio:

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ò controllare per l'uguaglianza bordi, data la maschera di bit (e un implicito un'etichetta-mapping). In alternativa, si può anche fare il controllo all'interno del if -. Basta controllare che data index corrente, la corrente G_1[0..index] sottografo è pari a G[bitmask] (con la stessa etichetta di mappatura implicita) prima recursing

Per N = 20, questo dovrebbe essere abbastanza veloce.

(aggiungere il memo, oppure si può riscrivere questo utilizzando Bottoms Up DP).

Answer 2

OK, devo fare la domanda ovvia. 1. Avete venti vertici. Camminare ogni grafico a fondo prima, ordine alfabetico tra     fratelli per ottenere le stringhe. 2. Un grafico è un sottografo di un'altra sse una stringa è in un'altra.

Quindi, che cosa si nasconde nella specifica problema per rendere questo fattibile?

Answer 3

È possibile visualizzare questo come un problema di allineamento. In sostanza si vuole trovare una mappatura iniettiva a che mappa ogni vertice in V_1 ad un vertice in V_2. Una mappa di allineamento a 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.

Credo che questo può essere formulato sotto forma di un numero intero lineari programma.