最小化图保持连通性

Question

我被一个图形问题困住了。我正在与OpenSG一起工作，并试图找出建筑物中两点之间的路径。

我构造了这个图：

​

我用它来寻找建筑物中两点之间的最短路径：

​

​

我就是这样找到这条路的：

• 我在图中添加开始/目标节点
• 我将开始/目标节点的边缘添加到所有可访问的节点(这是通过OSG中的IntersectAction完成的)
• 我使用A*-算法找到最短路径

我现在想把图最小化。如果两点之间的路径再长一点也没关系，我只想消除我现在的冗余。例如，可以删除所有浅绿色节点。房间里没有什么不“看”门的地方，所以不需要节点。它应该是这样的：

​

所以我有一个算法，它或多或少地做了我想做的事情，但我只是认为这一定是一个众所周知的问题。它不是最小顶点覆盖，因为例如，如果在最小顶点覆盖中不包括一个门节点，我就找不到在这两个房间之间的方法。

我比较了各种图表问题，但我找不到真正的匹配.

很晚了(早上6点20分)，我应该上床睡觉，也许这看起来有点混乱，或者可能是很明显的。谢谢你在这个问题上的任何投入。

Answer 1

我想我自己找到了答案。如果有人感兴趣的话。它不是一般的顶点覆盖，而是“最小连通顶点覆盖问题”(CVCP)。这方面有一篇很好的论文：

3-连通图中的顶点覆盖和连通顶点覆盖