我希望提出一种多项式时间算法，该算法采用图形 G 和整数 K 形式的输入，并确定 G 是否与 K 顶点相连。我认为这可能会利用深度优先搜索。我可以看到它怎么可能是非多项式解决方案，即只删除 K 个随机顶点，运行 DFS 来检查连通性，然后用另一组顶点再次执行此操作。 ~O(n^K) 的运行时间虽然有点多，但显然可以将其缩短为多项式时间。知道我在这里缺少什么吗？我想这与我们在运行 DFS 后获得的非树顶点有关，但我不完全确定我在寻找什么？提前致谢!
编辑:明确地说，我不是想要确定图形的连通性。相反，输入中给出了一个数字 k，我希望检查该图是否是 k 连通的。它不会产生一个给出图形连通性的答案，只是一个是或否。
最佳答案
您可以在多项式时间内计算输入图的顶点连通性，即使 k 不固定，参见 https://en.wikipedia.org/wiki/K-vertex-connected_graph#Computational_complexity
关于algorithm - 确定一个图是否是 K-vertex-connected，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10115114/