подграф ациклического графа, охватывающего некоторые выбранные узлы, но другие узлы не на пути

Question

У меня есть неориентированный и невзвешенный (или все ребра имеют вес 1) ациклический граф (G = VxE). Некоторые из узлов этого графа выбраны как sV (sV является подмножеством V). Проблема в том, что я хочу найти подграф, охватывающий все выбранные узлы. Естественно, некоторые не выбранные узлы могут быть покрыты. Но узлы, которые не находятся на желаемом подграфе, ограничены. Эти ограниченные узлы не должны быть в подграфе решения, если они не находятся только на одном пути между двумя выбранными узлами. Пример:

  A B C D
A - + + -
B + - + -
C + + - +
D - - + -

A, B, C, D - узлы, + представляет включение ребер. Для этого графа B и D выбраны узлы. Решение, которое я хочу для этого примера, состоит в следующем: подграф состоит из узлов B, C, D и ребер (B, C), (C, D) *. Обратите внимание, что А не в подграфе, как предполагалось. Какой подход помогает мне найти этот тип подграфов? Спасибо за идеи.

* (X, Y) представляет ребро между узлами X и Y.

Answer 1

Другой подход более ориентирован на дерево (так как дерево является ациклическим связным графом).

Допустим, вы структурировали граф в виде дерева, у вас есть:

• корень r
• из узла, способ извлечения его сыновей и его родителей (если есть)

Кроме того, для большего удобства я предположил, что вы можете добавить маркер наузлы (в самом узле / графике / дереве или в другой структуре на стороне).

Затем вы можете просто:

• добавить маркер для каждого узла, давая его число потомковкоторые находятся в sv (это можно сделать, поднявшись по дереву, начиная с разных элементов sv (ломаясь, когда вы встретите корень дерева))

• начиная с узла n:

  retrieve the sons with a number greater or equal to 1 # other sons are useless
  
  if there's no son with this property :
          stop
  else if there's only son s with this property :
          if n is in nv
                  add s to sv # s is needed to go to n
  else if there's many sons with this property :
          add n to sv # n is needed to join descendant of different branches
  foreach each son s
          start again from s
  

Я не особо задумывался об этом, но чувствую, что это может сработать.

Answer 2

Я чувствую, что неправильно понял проблему, но давайте попробуем.

Сначала мы должны предположить / проверить, что ваш график является связанным компонентом http://en.wikipedia.org/wiki/Connected_component_(graph_theory), а затем вы можете запустить:

solution = sV
foreach n1 in sv
    foreach n2 in sv, n2!=n1
        path = findPath(G,n1,n2)  
        // this should return at least one path because of connectivity
        // and no more than one
        for each n3 in path
            solution += n3

Он выполняет то, что вы хотите сделать?