c++ - 通过删除单个节点来降低图的连通性的最佳算法是什么？

Question

给定以下无向图：

不。节点数： 7 个
。边数： 6

边缘：

(0 1)
(1 2)
(2 3)
(2 4)
(4 5)
(4 6)

如您所见，此图是一个连接组件，任何节点都可以从任何其他节点访问。我想检测要删除的最佳节点，以使结果图具有最低的连通性（无法到达其他节点的最大对数）。在这种情况下，最好的节点是 2，因为它将产生 3 个分量 (0,1)、(3)、(4,5,6)，并且无法相互连接的对数为 11。

那么检测这个节点的最佳算法是什么？

标签： c++algorithmgraph

Answer 1

中介中心性是衡量图中有多少最短路径通过特定节点（或边）的量度。这通常在聚类中用于选择通过被移除而最断开图的边。这听起来与您想要做的非常相似。

有许多算法可以计算图中每个节点的中介中心性，例如Floyd-Warshall或 Brandes 算法。一旦你拥有所有节点的中介中心性（确保使用算法的节点多样性，而不是边缘节点），你应该选择具有最高值的节点，并将其从图中删除。