确定如果一个图是K-顶点连接 [英] Determining if a graph is K-vertex-connected

问题描述

我希望拿出一个多项式时间算法，需要在一个图，G和一个整数，K的形式输入，并确定摹是否为K-顶点相连。我想，这将有可能利用深度优先搜索。我可以看到它怎么会没有一个无多项式的解决方案，也就是，只有删除ķ随机顶点，运行DFS检查连接，然后用不同的组顶点的老毛病又犯了。的〜为O（n ^ K），运行时间是有点多，虽然，它显然可以把这个向下多项式时间。任何想法，我在这里缺少什么？我想它是与非树的顶点，我们运行的DFS后得到的，但我不能完全确定我在找什么？在此先感谢！

I'm looking to come up with an polynomial time algorithm that takes input in the form of a graph, G, and an integer, K, and determines whether G is K-vertex connected. I'm thinking that this would likely utilize Depth First Search. I can see how it could be none with a none-polynomial solution, i.e. just deleting K random vertices, running DFS to check for connectivity, and then doing it again with a different group of vertices. A run time of ~O(n^K) is a little much though, and it is apparently possible to bring this down to polynomial time. Any idea what I'm missing here? I imagine it has something to do with the non-tree vertices that we get after running a DFS, but I'm not totally sure what I'm looking for? Thanks in advance!

编辑：要清楚，我是的没有的寻找，确定图的连通性。相反，一些k被给予输入，我期待到检查图是K接通。它会的没有的产生一个答案，让图的连通性，只是一个是或否。

To be clear, i am not looking to determine the connectivity of the graph. Rather, a number, k, is given on input and I am looking to check if the graph is k connected. It will not produce an answer that gives the connectivity of the graph, just a yes or no.

推荐答案

您的可以的计算顶点连接在多项式时间输入图形，即使当k是不固定的，看的https://en.wikipedia.org/wiki/K-vertex-connected_graph#Computational_complexity

You can compute vertex-connectivity for an input graph in polynomial time, even when k is not fixed, see https://en.wikipedia.org/wiki/K-vertex-connected_graph#Computational_complexity

这篇关于确定如果一个图是K-顶点连接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！