Поиск подграфа на графике

Question

У меня есть график, показанный здесь. Просто для узла, что узлы B_0, B_1, принадлежат узлу типа B, C_0, C_1. C_2, C_3 принадлежат узлу типа C и т. Д. Теперь я хочу, чтобы найти несколько подграфов, которые могли бы отвечают соответствующим требованиям критериев, как определено в этом примере -

Criteria -

1. подграф содержит 1 узел типа А, 1 узел типа B, 1 узел типа C, один узел типа D.
2. подграф имеет один край от узла типа A до одного узла типа B, один тип подключения к краю B и тип C и один тип соединения типа C и тип D.
3. подграф содержит один край от типа A, выходящий из подграфа, к узлу типа B, один край от типа B до узла типа C снаружи, один край от типа D до типа E снаружи.

Теперь это описание должно дать результат, -

1. подграф :: A_0, B_0, C_1, D_1
2. подграф :: A_0, B_0, C_0, d_0
3. подграф :: A_0 , B_1, C_2, D_2
4. подграф :: A_0, B_1, C_3, D_3

Я хочу знать, если есть какой-либо алгоритм, б y, на котором я могу найти такие подграфы? Я попытался вычислить алгоритм, выполнив все возможные комбинации. Однако это будет экспоненциально для количества узлов в подграфе. Таким образом, я хочу знать, существует ли эффективный способ его вычисления. Или, если в теории графов существует проблема подобного характера?

Answer 1

Вы можете начать с посещения всех узлов типа А. Для каждого узла, смотрите на все узлы, подключенные к ним, которые имеют тип B. Отсюда выглядят все узлы типа C и так далее, отслеживание узлов, которые вы посетили с последнего узла A. Затем, когда вы достигаете субнода, который завершает критерии вашего поиска, вы добавляете весь список узлов из узла A до той точки, где вы находитесь. По сути, вы делаете поиск по глубине, в котором вы продолжаете перемещаться по графику, если узел соответствует критериям того, что следует следовать, и возвращаться назад, когда не существует более достоверных узлов (т. Е. Создающих действительный подграф), выходящих из ваш текущий узел.