如何定义与埃德蒙兹卡普的剪辑集？

Question

我正在使用JGraphT，我使用EdmondsKarpMFImpl。

问题是:如何定义所有的边缘--什么是“参与”？

我试着使用getCutEdges方法，但它只返回1边。

我有以下图表：

(所有边都有一个权重值(1)和一个剩余容量值(10))

public SimpleDirectedWeightedGraph generateAbilene(){

        Supplier<Integer> vSupplier3 = new Supplier<Integer>() {

            private int id = 1;

            @Override
            public Integer get() {
                return id++;
            }
        };

        SimpleDirectedWeightedGraph exGraph3 =
                new SimpleDirectedWeightedGraph<Integer, MyDefaultWeightedEdge>(vSupplier3, MyUtil.createDefaultWeightedEdgeSupplier());


        exGraph3.addVertex(1);
        exGraph3.addVertex(2);
        exGraph3.addVertex(3);
        exGraph3.addVertex(4);
        exGraph3.addVertex(5);
        exGraph3.addVertex(6);
        exGraph3.addVertex(7);
        exGraph3.addVertex(8);
        exGraph3.addVertex(9);
        exGraph3.addVertex(10);
        exGraph3.addVertex(11);


        exGraph3.addEdge(1,2);
        exGraph3.addEdge(1,7);
        exGraph3.addEdge(2,3);
        exGraph3.addEdge(3,4);
        exGraph3.addEdge(4,5);
        exGraph3.addEdge(6,7);
        exGraph3.addEdge(10,7);
        exGraph3.addEdge(7,8);
        exGraph3.addEdge(8,5);
        exGraph3.addEdge(8,9);
        exGraph3.addEdge(8,11);
    return exGraph3; 
}

使用该方法，我只得到源节点(1)和Sink节点(5)之间的前2边(1-2和1-7)。

我想拿回所有的边缘在最小的切割。例如，在上述情况下，它应该返回: 1-2，1-7，2-3，7-8，3-4，8-5，4-5 (关于我不关心的边的顺序)。

图如下所示：

​

​

Answer 1

我认为你误解了最低削减的定义。(加权)最小割集是两个不相交子集(例如S和T)中顶点的划分，使得与该分区相交的边的权重之和最小。在您的情况下，您特别要求最小的s-t切割，这是最小割集的一个特定情况:在最小的cut割集中，您要求源顶点是S的成员，而接收器顶点T是T的成员。请注意，在图中找到最小割集的更一般问题可以得到一个解，其中顶点s和t都在同一个分区中。

查看您的图，使用s=1和t=5的最小s-t切分是: S={1,2,6,7,10}和T={3,4,5,8,9,11}。穿过这些分区的边( 2，3，(7,8))的总权重为2，因此这个割集的值为2。类似地，您可以用相同的值识别这个图中的其他so割集。

现在，最大流量最小切割定理告诉我们切分和流之间的关系。如果我们用s=1和t=5计算图中的最大s流，则最大流最小切割定理告诉我们，从s到t的最大流量不能超过2个单位。图中的一个最大流的例子是:我们在路径1-7-8-5上发送一个流量单位，在路径1-2-3-4-5上发送一个单位，结果总流量为2。

所以，你似乎在寻找的，不是最小切割问题的解决方案，而是最大流量问题的解决方案。特别是，您想要计算最大流问题中的哪些边有一个正流值。当然，您可以使用JGraphT来获得这些结果。下面是您的示例的清理版本：

public static void maxFlowMinCutExample(){
    Graph<Integer, DefaultWeightedEdge> graph =
            new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);
    Graphs.addAllVertices(graph, Arrays.asList(1,2,3,4,5,6,7,8,9,10,11));

    //NOTE: by default, edges in jgrapht have a weight of 1.0. You would invoke graph.setEdgeWeight(.)
    //to change the edges' weight.
    graph.addEdge(1,2);
    graph.addEdge(1,7);
    graph.addEdge(2,3);
    graph.addEdge(3,4);
    graph.addEdge(4,5);
    graph.addEdge(6,7);
    graph.addEdge(10,7);
    graph.addEdge(7,8);
    graph.addEdge(8,5);
    graph.addEdge(8,9);
    graph.addEdge(8,11);

    //Calculate a Minimum Cut:
    minCut(graph, 1, 5);
    //Calculate a max flow:
    maxFlow(graph, 1, 5);
}

public static void minCut(Graph<Integer, DefaultWeightedEdge> graph, Integer source, Integer sink){
    MinimumSTCutAlgorithm<Integer, DefaultWeightedEdge> mc = new EdmondsKarpMFImpl<>(graph);
    System.out.println("Minimum s-t cut weight: "+mc.calculateMinCut(source, sink));
    System.out.println("Source partition S: "+mc.getSourcePartition());
    System.out.println("Sink partition T: "+mc.getSinkPartition());
    System.out.println("Cut edges (edges with their tail in S and their head in T): "+mc.getCutEdges());
}

public static void maxFlow(Graph<Integer, DefaultWeightedEdge> graph, Integer source, Integer sink){
    MaximumFlowAlgorithm<Integer, DefaultWeightedEdge> mf = new EdmondsKarpMFImpl<>(graph);
    MaximumFlowAlgorithm.MaximumFlow<DefaultWeightedEdge> flow = mf.getMaximumFlow(source, sink);
    System.out.println("Max flow value: "+flow.getValue());
    System.out.println("Edges with positive flow:");
    for(DefaultWeightedEdge edge : graph.edgeSet())
        if(flow.getFlow(edge) > 0)
            System.out.println("Edge: "+edge+" value: "+flow.getFlow(edge));
}

上述代码的输出：

Minimum s-t cut weight: 2.0
Source partition S: [1]
Sink partition T: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Cut edges (edges with their tail in S and their head in T): [(1 : 2), (1 : 7)]
Max flow value: 2.0
Edges with positive flow:
Edge: (1 : 2) value: 1.0
Edge: (1 : 7) value: 1.0
Edge: (2 : 3) value: 1.0
Edge: (3 : 4) value: 1.0
Edge: (4 : 5) value: 1.0
Edge: (7 : 8) value: 1.0
Edge: (8 : 5) value: 1.0