Contando instancias de subgraph

Question

Digamos que tengo un gráfico grande (varios miles de nodos) dirigidos GRAMO y un gráfico mucho más pequeño (3-5 nodo) dirigido gramo. Quiero contar cuántos isomorfismos de gramo están en GRAMO. En otras palabras, quiero saber cuántos conjuntos únicos de nodos en GRAMO juego gramo. Me doy cuenta de que esta es una instancia del problema del isomorfismo del subgrafio y, por lo tanto, es NP complete. Sin embargo, dado que puede suponer que gramo es pequeño, ¿hay algún algoritmo razonablemente eficiente para hacer esto?

Answer 1

Aunque el isomorfismo gráfico es NP-NP en general, los problemas que encuentras en el mundo real a menudo son bastante fáciles. Una simple fuerza bruta debería ser suficiente: dejar M_i ser un conjunto de mapas de los primeros nodos I de G a los nodos de G. Comience con m_0 que contiene el mapa vacío y extiéndalo un nodo a la vez, descartando cualquier mapas que viole la restricción x->y IFF m(x)->m(y).

Querrá pedir los nodos en G para que mucha poda ocurra temprano. Suponiendo que sus gráficos sean bastante escasos, querrá un pedido que complete tantos bordes lo antes posible, tal vez un DFS del nodo de más alto grado.