我有一个无向且未加权(或所有边都加权为 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 之间的边。