Compter les instances de sous-graphe

Question

Disons que j'ai un grand (plusieurs milliers de nœuds) dirigée graphique g et un graphique dirigé beaucoup plus petit (3-5 nœuds) g. Je veux compter combien d'isomorphismes de g sont dans g. En d'autres termes, je veux savoir combien d'ensembles uniques de nœuds g match g. Je me rends compte qu'il s'agit d'une instance du problème de l'isomorphisme de sous-graphe et est donc NP-Complete. Cependant, étant donné que vous pouvez supposer que g Est-ce petit, y a-t-il un algorithme raisonnablement efficace pour ce faire?

Answer 1

Bien que l'isomorphisme graphique soit NP-Complete en général, les problèmes que vous rencontrez dans le monde réel sont souvent assez faciles. Une simple force brute devrait suffire: laissez M_i être un ensemble de cartes des premiers nœuds de G en g aux nœuds de G. Commencez par m_0 contenant la carte vide et prolongez-le un nœud à la fois, jetant toutes les cartes qui violent la contrainte x->y fic m(x)->m(y).

Vous voudrez commander les nœuds en G afin que beaucoup d'élagage se produise tôt. En supposant que vos graphiques sont assez rares, vous voudrez une commande qui complète autant de bords le plus tôt possible, peut-être un DFS du nœud de degré le plus élevé.