1

对不起，文字墙，它尽可能简洁！

我有一个非常大的有向图 G 和 G 内的顶点子集 S p 和 G 中的一个顶点 q，即在诱导子图中这两个顶点之间存在一条边。这是关键；它比通常的诱导子图问题更复杂（我认为）。

我能想到的解决问题的最基本方法如下（我意识到它可能不是最有效的，如果您有其他不太复杂的建议，请告诉我）： 对于 S 中的每一对顶点，在 G 中测试它们之间是否存在路径。如果存在这样的路径，则在诱导子图中插入 p 和 q 之间的边。就我的目的而言，n^2 次还不错。

所以，我想我有两个问题：1）确定两个顶点之间是否存在路径的最快方法是什么？我不需要知道路径，只需要知道它是否存在。此外，如果我可以对整个图形进行一些预处理以加快计算速度，那可能是什么，因为我必须在每对顶点之间执行此计算？

2）有没有比我建议的更快的方法来找到我描述的诱导子图的类型？

非常感谢你的帮忙！

4

1 回答 1

1

查找两个顶点之间是否存在路径的问题称为传递闭包问题，在一般情况下与矩阵乘法一样困难。我将首先在您的图上运行一个强连接组件算法，以将循环压缩到单个节点并形成有向图。如果你幸运的话，你会有一些大循环，这将使随后的传递问题变得容易。然后我会在该图上运行 Floyd Warshall 所有对最短路径算法来计算传递闭包，因为它的编码非常简单。也许基于 o(n^3) 矩阵乘法的算法之一会更快，但我怀疑它会更快，因为常数太低 Floyd Warhsall。

这是强连通分量的快速算法。

这包含了矩阵乘法和传递闭包等价的证明。

我不确定是否有任何好的方法可以绕过计算传递闭包来解决您的原始问题。我怀疑不是，但另一方面，有时聪明的人会想出一些很棒的东西。

于 2011-06-03T01:20:27.753 回答