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

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) *. Обратите внимание, что A не находится в подграфе, как предполагалось. Какой подход помогает мне найти этот тип подграфов? Спасибо за идеи.

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

Answer 1

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

Во-первых, мы должны предполагать/проверить, что ваш график является связной компонентой 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 

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

Answer 2

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

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

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

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

Тогда вы можете просто:

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

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

  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 
  

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