如何判断带权的二分图是否可分？
How to judge whether a bipartite graph with weight is separable?
我想判断一个二分图是否可分，当存在一个顶点的权值小于或等于阈值时。例如，选择 0.2 作为阈值。
图1)中有一个红色的顶点权重小于0.2。二部图可以分成三个子图，将红色顶点分别复制到三个子图中。
在图2)中，还有一个权重小于0.2的红色顶点。但是，红边导致二分图没有拆分成子图。
我的想法：
复制权重小于或等于阈值的顶点（名为lowVer，红色）和link复制顶点分别到关联顶点（绿色边） .关联顶点是与顶点lowVer.
从顶点lowVer（黄色边）断开连接。
判断二分图是否可分depth-first-search
有没有更好的方法？
如果我理解得很好，你想要知道给定的顶点（小于阈值的那个）是否是一个关节点。关节点是一个顶点，当它从图中移除时，会增加连通分量的数量。
如果我正确地表达了你的问题，那么有很多算法可以找到关节点，例如 https://en.wikipedia.org/wiki/Biconnected_component#Other_algorithms or https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
有很多方法可以解决这个问题。
让我们选择权重为 0.1 的节点并将其作为图的根。
image
现在如果叶节点的度数为 1 ，则其可分离
否则，它是不可分离的。
如果我遗漏了什么，请告诉我..
我想判断一个二分图是否可分，当存在一个顶点的权值小于或等于阈值时。例如，选择 0.2 作为阈值。
图1)中有一个红色的顶点权重小于
0.2。二部图可以分成三个子图，将红色顶点分别复制到三个子图中。在图2)中，还有一个权重小于
0.2的红色顶点。但是，红边导致二分图没有拆分成子图。
我的想法：
复制权重小于或等于阈值的顶点（名为
lowVer，红色）和link复制顶点分别到关联顶点（绿色边） .关联顶点是与顶点lowVer. 相连的顶点
从顶点
lowVer（黄色边）断开连接。判断二分图是否可分
depth-first-search
有没有更好的方法？
如果我理解得很好，你想要知道给定的顶点（小于阈值的那个）是否是一个关节点。关节点是一个顶点，当它从图中移除时，会增加连通分量的数量。
如果我正确地表达了你的问题，那么有很多算法可以找到关节点，例如 https://en.wikipedia.org/wiki/Biconnected_component#Other_algorithms or https://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
有很多方法可以解决这个问题。 让我们选择权重为 0.1 的节点并将其作为图的根。
image
现在如果叶节点的度数为 1 ，则其可分离 否则，它是不可分离的。
如果我遗漏了什么，请告诉我..