0

我有一个无向且未加权（或所有边都加权为 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) 表示节点 X 和 Y 之间的边。

4

2 回答 2

0

我觉得我误解了这个问题，但让我们试一试。

首先，我们必须假设/检查您的图表是一个连接组件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

它是否执行您想做的事情？

于 2012-01-11T12:15:06.567 回答
0

另一种方法更面向树（因为树是无环连通图）。

假设您已将图形构建为树，您有：

  • 一个根 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

我并没有真正考虑过，但我觉得这可以工作。

于 2012-01-11T14:46:49.553 回答