这是一个询问图的边缘连通性与其最小切割之间的联系的问题。
众所周知，无向图的边连通性是k为断开图而必须移除的最小边数。例如，树的边连通性为 1，环的边连通性为 2。
我的想法是最小切割的容量应该等于边缘连接。因为割就是把一个图分成两个不连贯的部分。如果我们知道边的连通性k，则意味着我们必须至少删除或切断k边才能使图分成两个不连贯的部分。因此最小切割的容量应该是k。
我还没有找到关于这个问题的任何结论或证据，所以我在这里问。谁能检查我的想法是否正确或给我任何其他想法？
问问题
494 次