Un moyen facile de déterminer si un graphe donné est sous-graphe d'un autre graphique?

Question

Je cherche un algorithme pour vérifier si un graphe donné est sous-graphe d'un autre graphique donné.

Je quelques conditions pour faire ce bit problème NP complet plus possible ..

• Les graphiques ont environ <20 sommets.
• Les graphiques sont DAG.
• Tous les sommets sont non étiquetés uniquement, et les sommets correspondants dans le graphique principal et le sous-graphe doivent avoir la même étiquette. Je ne sais pas si j'utilise les terminologies correctes (parce que je ne l'ai pas suivi un cours de théorie des graphes ...). Ce sera quelque chose comme:

Le graphique de la ligne A - B est sous-graphe de A - B - A, mais A - A ne soit pas un sous-graphe de A - B -. A

Toutes les suggestions sont très bien. Ce n'est pas une question de devoirs btw. : D

Answer 1

Si les étiquettes sont uniques, pour un graphe de taille N, il y a des bords O(N^2), en supposant qu'il n'y a pas de boucles indépendantes ou plusieurs arêtes entre chaque paire de sommets. Utilisons E pour le nombre d'arêtes.

Si vous hachez les bords fixés par le graphique parent, vous pouvez passer par les bords de la sous-graphes, vérifier si chacun est dans la table de hachage (et dans la bonne quantité, si on le souhaite). Vous faites cela une fois pour chaque bord, donc O(E).

Appelons le graphique G (avec des sommets de N) et la possible sous-graphe G_1 (avec des sommets de M), et que vous voulez trouver G_1 is in G.

Étant donné que les étiquettes ne sont pas uniques, vous pouvez, avec la programmation dynamique, construire les sous-problèmes en tant que tels au lieu - au lieu d'avoir sous-problèmes de O(2^N), un pour chaque sous-graphe, vous avez O(M 2^N) sous-problèmes - un pour chaque sommet G_1 (avec des sommets de M ) avec chacun des sous-graphes possibles.

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

et les états sont définis comme tels:

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

avec le cas de base étant index = M, et vous pouvez vérifier l'égalité des bords, compte tenu de la bitmask (et une étiquette-mapping implicite). Vous pouvez également faire la vérification au sein de l'instruction if -. Il suffit de vérifier que index courant donné, le G_1[0..index] de sous-graphe courant est égale à G[bitmask] (avec le même mappage d'étiquette implicite) avant récursion

Pour N = 20, cela devrait être assez rapide.

(ajoutez votre mémo, ou vous pouvez réécrire ce à l'aide de fonds jusqu'à DP).

Answer 2

OK, je dois poser la question évidente. 1. Vous avez vingt sommets. Marchez chaque graphique en profondeur d'abord, par ordre alphabétique parmi     frères et sœurs pour obtenir des chaînes. 2. Un graphe est un sous-graphe d'un autre ssi une chaîne est dans une autre.

Alors, ce qui se cache ailleurs dans le cahier des charges de problème pour effectuer ce infaisable?

Answer 3

Vous pouvez considérer cela comme un problème d'alignement. Fondamentalement, vous voulez trouver une application injective a qui associe tous les sommets de V_1 à un sommet en V_2. Une carte d'alignement a peut être marqué comme suit:

s (a) = \ _ {somme (v, w) \ in E_1} \ sigma (v, w, a (v), a (p)),

où \ sigma (v, w, a (v), a (w)) = 1, si (a (v), a (p)) \ in E_2 sinon il est égal à 0.

Je pense que ceci peut être formulé sous la forme d'un programme linéaire entier.