algorithm - 计算图的顶点连通性

Question

是否有一种算法可以在给定图时计算该图的顶点连通性（为了将图分成两个连通图而要删除的最小顶点数）。（请注意，图表可能已经断开连接）。谢谢！

Answer 1

请参阅： 确定图是否为 K 顶点连接

图的 k 顶点连通性

当你将它与二分搜索结合起来时，你就完成了。

Answer 2

这本书的章节应该有你开始需要的一切；它基本上是对确定图的边连通性和顶点连通性的算法的调查，其中描述了算法的伪代码。第 12 页概述了可用算法以及复杂性分析和参考。一般情况下的大多数解决方案都是基于流的，除了一种随机算法。不同的通用解决方案针对图的不同属性进行了优化，因此您可以预先选择最渐近有效的解决方案。此外，对于某些类别的图，存在比一般解决方案提供的复杂度更高的专门算法。