|
Find all minimal edge cuts of a connected undirected graph using fundamental cutsets. (Assume no self-loops or multiple edges.)
The MinimalEdgeCuts procedure is in the startup code edit region (See Edit -> Startup Code.) (and is reproduced at the end of the worksheet).
| > |
|
| > |
|
Choose a graph.
| > |
![G := Graph({{1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}}); DrawGraph(G, size = [200, 200])](/view.aspx?sf=219618_post/b9e1b40d55341ab383450be4b06f4bc5.gif)
|
![GRAPHLN(undirected, unweighted, [1, 2, 3, 4], Array(1..4, {(1) = {2, 3, 4}, (2) = {1, 3}, (3) = {1, 2, 4}, (4) = {1, 3}}), `GRAPHLN/table/1`, 0)](/view.aspx?sf=219618_post/33051d06c2691a2ff0dfa26732eebc77.gif)
The objective is to find all minimal edge cuts. If we partition the vertices of a graph in two non-empty sets (parts), then a cut is defined as a set of edges of the graph that have one end in the first part and the other end in the second part. Removal of these edges breaks the graph into two (or more) disconnected components.
For example the cut with edges {1,2} and {2,3} leaves two components with vertices [1,3,4] in one component and vertex [2] in the other component.
| > |
![cut := {{1, 2}, {2, 3}}; IsCutSet(G, cut); DrawGraph(DeleteEdge(G, cut, inplace = false), size = [200, 200])](/view.aspx?sf=219618_post/f1d59b741872256038fee35e8402622c.gif)
|
A cut is minimal if adding back any of the edges makes it connected again, i.e, the cut leave only two components. The above cut is minimal. Sometimes the term cutset is used to mean a minimal cut, but sometimes, as in Maple's IsCutSet, cutset means any removal of edges that increases the number of components.
This graph has 6 minimal cuts:
| > |
|
](/view.aspx?sf=219618_post/bfdde32d35654b95ff289cb01eb72e9c.gif)
This partitioning process suggests a brute force algorithm to find all minimal cuts. Find all partitions of the vertices into two (non-empty) sets. The two induced subgraphs  and  have some of the edges of the graph. All edges of the graph that are not in the two subgraphs form a cut. For example for the above partition we have:
| > |
![partition := [[1, 3, 4], [2]]; G__1 := InducedSubgraph(G, partition[1]); 'Edges(G__1)' = Edges(G__1); G__2 := InducedSubgraph(G, partition[2]); 'Edges(G__2)' = Edges(G__2); cut := `minus`(`minus`(Edges(G), Edges(G__1)), Edges(G__2))](/view.aspx?sf=219618_post/b06fa55b5df80d9e16d8f878ec1dbe92.gif)
|
![[[1, 3, 4], [2]]](/view.aspx?sf=219618_post/e3ded8c07bf52576789f9b59dcbc3dcc.gif)
Now we have to check that each component is connected, or that there are a total of two components. Since there are in this case, the cut is minimal.
| > |
|
Note that we do have to test that there are only two components. For example for the path graph 1--2--3, the partition [[2],[1,3]] has three components (the three individual vertices). The associated cut {{1,2},{2,3}} is not minimal because we could put edge {1,2} back and the graph would still be disconnected.
The number of partitions to be tested is  , where n is the number of vertices. Any subset of the vertices could be in the first set (except the empty set and the set of all vertices), and then the other vertices must be in the second set. However that will give double the possibilities, since swapping set 1 and set 2 makes no difference. In the present case there are  possibilities, as seen below, where 0 indicates that the vertex in that position is in set 1 and 1 indicates that it is in set 2. For example, possibility 4 is the above partition ![[[1, 3, 4], [2]]](/view.aspx?sf=219618_post/befc7e9fa19267754c01e6704bc8a322.gif) .
| > |
|
1 2 3 4
1: 0 0 0 1
2: 0 0 1 0
3: 0 0 1 1
4: 0 1 0 0
5: 0 1 0 1
6: 0 1 1 0
7: 0 1 1 1
The algorithm described is implemented as procedure MinimalEdgeCutsPartition in the startup code. (The minimal cuts are not produced in the same order as above.)
However, a better approach is by building up the cuts fron a set of fundamental cuts (or cutsets, using the word in the restrictive sense). These are associated with a spanning tree. We choose any spanning tree, which we highlight with red edges. This is a tree graph (connected with no cycles) that has the same vertices as the graph.
| > |
![treeG := SpanningTree(G); HighlightEdges(G, treeG); DrawGraph(G, size = [200, 200])](/view.aspx?sf=219618_post/dcec7d048d882dc2e01283be93d0a9e7.gif)
|
![GRAPHLN(undirected, unweighted, [1, 2, 3, 4], Array(1..4, {(1) = {2, 3, 4}, (2) = {1}, (3) = {1}, (4) = {1}}), `GRAPHLN/table/23`, 0)](/view.aspx?sf=219618_post/da6f3afd639672335126ac221fdeed2a.gif)
Any spanning tree graph has  edges. This is also the number of vertices minus the number of connected components (=1), which is the rank of the graph, which we will call  .
We will find one fundamental cutset for each edge of the tree, so there will be  fundamental cutsets.
| > |
|
Select one of the tree edges, say {1,2}. Removal of this edge partitions the tree into two components. We find the vertex partition and the corresponding cut by the procedure above. (We do not have to test for only two components because that follows from the tree structure.). This is the example we did above. The first three cuts in mincuts are the fundamental ones. Each one has one of the tree edges.
| > |
![f[1], f[2], f[3] := entries(mincuts[1 .. 3], nolist)](/view.aspx?sf=219618_post/75bc804fbceb98be08b9a828d49e50b4.gif)
|
It is possible to generate all the cuts of the graph involving the tree edges by taking all  subsets of the set of fundamental cutsets (this includes the empty set), and adding the elements of each subset with a ring sum operation.
A ring sum of two edge sets includes all edges in both sets except those that are common to both (the symmetric difference or disjunctive union):
| > |
|
(Maple has this as the symmdiff command, but not in infix form.)
We can also represent a set of edges by a vector, with entry 1 if the corresponding edge is in the set and 0 otherwise. The edge order we choose here is the order in  . Then the ring sum operation is the same as addition modulo 2 of the corresponding vectors, though we won't make much use of this in implementing the algorithm. Set up to convert to vectors.
| > |
])); tovec := proc (edges) options operator, arrow; Vector(e, `~`[`=`](map(proc (x) options operator, arrow; edgetable[x] end proc, edges), 1)) end proc](/view.aspx?sf=219618_post/16377c79748aff070b2be8f9587d57a5.gif)
|
Let's try the ring sum on f[1] and f[2]. It is a cut, and since it now has two tree edges it is not a fundamental cut. (It happens to be minimal because it splits the graph into two components.)
| > |
![f[1]*`⊕`*f[2] = `⊕`(f[1], f[2]); IsCutSet(G, rhs(%))](/view.aspx?sf=219618_post/01ac810ebd240e0eb90c94f972ba72fb.gif)
|
Do the same thing in the vector representation. The same logic about the tree edges (first three entries) shows the fundamental vectors are basis vectors and the three vectors  are linearly independent (with respect to the addition mod 2 operation).
| > |
![V[1], V[2], V[3] := tovec(f[1]), tovec(f[2]), tovec(f[3]); '`mod`(V[1]+V[2], 2)' = `mod`(V[1]+V[2], 2)](/view.aspx?sf=219618_post/c8cba8b67477709880f994cd9d971ec4.gif)
|
![V[1], V[2], V[3] := Vector(5, {(1) = 1, (2) = 0, (3) = 0, (4) = 1, (5) = 0}), Vector(5, {(1) = 0, (2) = 1, (3) = 0, (4) = 1, (5) = 1}), Vector(5, {(1) = 0, (2) = 0, (3) = 1, (4) = 0, (5) = 1})](/view.aspx?sf=219618_post/54073a52791356ce2f4ff05044426841.gif)
![`mod`(V[1]+V[2], 2) = Vector[column](%id = 36893490386597633668)](/view.aspx?sf=219618_post/852f312c952d643fb7ccdac29210ed8e.gif)
The ring sum of any two cuts is another cut, which may be minimal (a cutset) or a disjoint union of cutsets (= two cutsets together). Combining the elements of the 8 subsets gives the eight cuts for this graph associated with the chosen tree graph, i.e., it has all combinations of tree edges. In vector form they are:
| > |
![cutvecs := seq(seq(seq(`mod`(i*V[1]+j*V[2]+k*V[3], 2), `in`(i, [0, 1])), `in`(j, [0, 1])), `in`(k, [0, 1]))](/view.aspx?sf=219618_post/2dd69f7553f0e4dd5a70e08360578e8b.gif)
|
, Vector[column](%id = 36893490386597647052), Vector[column](%id = 36893490386597647772), Vector[column](%id = 36893490386597648252), Vector[column](%id = 36893490386597648972), Vector[column](%id = 36893490386597649452), Vector[column](%id = 36893490386597649932), Vector[column](%id = 36893490386597650172)](/view.aspx?sf=219618_post/ea17903cd4a5fc87bee2d10162643a58.gif)
Although we constructed these cuts relative to a specific spanning tree, they can be shown to be all the cuts of the graph. Consider the set of all edges of the graph. It might seem that this is a cut that has been missed, because it separates the graph into two or more (actually 4) components. However, looking at the edges
| > |
|
and recalling the definition of a cut, we see that this is not actually a cut. We need the edges in a cut all to have one end in one set of vertices and the other end in the set of other vertices, and this is not possible here. (Maple's IsCutSet is not this strict and returns true.) We can show it is not possible with IsBipartite.
| > |
|
Although we have found all cuts, we now need to test them to find which ones are minimal. The first case with no edges does not cut the graph into two components and we reject it. (It is usually included as a cut to make the cuts into a vector space.) The 6th one is not minimal. Its first and third entries are 1, meaning it is the ring sum of the first and third fundamental cuts. It splits the graph into three components:
| > |
![cut := `⊕`(f[1], f[3]); DrawGraph(DeleteEdge(G, cut, inplace = false), size = [200, 200])](/view.aspx?sf=219618_post/9cb16fc3748e50bf3388ab7b9312c6dc.gif)
|
This is a case where the ring sum is a disjoint union (not minimal), and arises because f[1] and f[3] have no edges in common:
| > |
![`intersect`(f[1], f[3])](/view.aspx?sf=219618_post/ac974e27771e211ce1e518132aa621e0.gif)
|
For the present graph, all but the empty set and ![`⊕`(f[1], f[3])](/view.aspx?sf=219618_post/e81f6eac5d38398f80dc2299b057aaab.gif) are minimal, and so there are 6 minimal cuts. In vector form:
| > |
![cutvecs := convert(map(tovec, mincuts), set)[]](/view.aspx?sf=219618_post/1f71c1a4db66ebe7105b8fc8656b528a.gif)
|
, Vector[column](%id = 36893490386597690652), Vector[column](%id = 36893490386597690772), Vector[column](%id = 36893490386597690892), Vector[column](%id = 36893490386597691012), Vector[column](%id = 36893490386597691132)](/view.aspx?sf=219618_post/16e7c605d476af5d02f2c2785d646f7a.gif)
So the algorithm is to generate all cuts and test them for minimality. If we neglect the empty cut, then we have to generate  cuts for testing. This is the same as the number of partitions that we generated in the partition algorithm. However, for the fundamental cuts we do not need to test that the components are connected, and more importantly, the ring sum is a more efficient way of finding the edges than partitioning and then using InducedSubgraphs.
The tests for minimality can be made more efficient by finding cases that can be classified without having to check the number of components. Two simple cases with modest savings (implemented here) are:
1. The fundamental cuts are minimal by construction.
2. If two cuts have no edges in common, then the ring sum is a disjoint union and is not minimal. This is the case for example for f[1] and f[3].
There may be other ways to classify without doing the more difficult minimality test, for example variations of (2.) for ring sums with more than two cuts. Hovever, the cutset algorithm is already significantly more efficient than the partition algorithm. Perhaps working with the vectors would be more efficient. Other more efficient algorithms may be known that I am not aware of.
The MinEdgeCuts algorithm in the startup code is reproduced here:
| > |
MinimalEdgeCuts:=proc(G::GRAPHLN)
local mincutsets,n,edges,treeedges,treeG,
i,j,r,vertexpartition,partitionedges,nf,fc,
fsets,ref,fcutsets,cutsetedges;
uses GraphTheory;
if not IsConnected(G) then return Vector([]) end if;
n:=NumberOfVertices(G);
edges:=Edges(G);
# choose a spanning tree and find corresponding fundamental cutsets
treeG:=SpanningTree(G);
treeedges:=Edges(treeG);
r:=n-1; # =nops(treeedges) = GraphRank(G)
mincutsets:=table(); # first r ones are the fundamental ones
for j to r do
vertexpartition:=ConnectedComponents(DeleteEdge(treeG,treeedges[j],'inplace'=false));
partitionedges:=`union`(map(Edges,map2(InducedSubgraph,G,vertexpartition))[]);
mincutsets[j]:=edges minus partitionedges;
end do;
j:=r;
# now find ringsums of all subsets of the set of fundamental cutsets
fsets := Iterator:-BinaryGrayCode(r,'rank'=2); #skip empty set
for ref in fsets do;
fcutsets:=seq(ifelse(ref[i]=1,mincutsets[i],NULL),i=1..r);
nf:=nops([fcutsets]);
if nf=1 then
next # fundamental cutsets already in mincutsets
elif nf=2 and (fcutsets[1] intersect fcutsets[2] = {}) then
next # pair of disjoint cutsets not minimal
# todo other detections of non-minimal cutsets
else # rest the hard way
cutsetedges:=fcutsets[1];
for i from 2 to nf do
fc:=fcutsets[i];
cutsetedges:=(cutsetedges union fc) minus (cutsetedges intersect fc);
end do;
vertexpartition:=ConnectedComponents(DeleteEdge(G,cutsetedges,'inplace'=false));
if nops(vertexpartition)=2 then # cutset is minimal
j:=j+1;
mincutsets[j]:=cutsetedges
end if
end if;
end do;
Vector(j,mincutsets);
end proc:
|
| > |
|
|
