如何判断具有权重的二部图是否是可分的？

Question

当存在一个权小于或等于阈值的顶点时，我想确定一个二分图是否是可分的。例如，选择0.2作为阈值。

​

​

• 在图1中，有一个具有红色的顶点，其权重小于0.2。将二部图分为三个子图，将红色顶点分别复制到三个子图中。
• 在图2中，还有一个具有红色的顶点，其权重小于0.2。然而，红色边导致二部图不被分割成子图。

我的想法：

1. 复制权重小于或等于阈值的顶点(名为lowVer，红色)，并将重复顶点分别链接到相关顶点(绿色边)。关联顶点是连接到顶点lowVer的顶点。
2. 从顶点lowVer(黄色边缘)断开连接。
3. 用depth-first-search判断二部图是否是可分的

​

​

有更好的办法吗？

Answer 1

如果我理解得很好，你想知道的是，给定的顶点(小于阈值的顶点)是否是一个交点。连接点是一个顶点，当从图中移除时，就会增加连通分量的数量。

如果我正确地描述了您的问题，那么有许多算法可以找到发音点，例如算法或https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/。

Answer 2

有很多方法可以解决这个问题。让我们选择0.1个权重的节点，并将其放在图的根上。

图像

现在，如果叶节有1度，它的其他可分离的，它是不可分离的。

如果我错过了什么让我知道..。