The background of my question comes from graph theory. But the essence of the problem has nothing to do with graph theory, and it only involves programming.
For the graph g1 below, the paired crossing edges are marked as wine red.
with(GraphTheory):
with(SpecialGraphs):
g:=CompleteGraph(6);
g1:=DeleteEdge(g, {3,2}, inplace = false);
Paircrossedges:=[[{1,6},{3,5}],[{2,5},{1,4}],[{2,6},{3,4}]];
For each pair of crossed edges, I choose one to delete and get a plane graph g1', and then I consider the edge connectivity of g1', if the edge connectivity is equal 3, stop the calculation and return to the deleted edge set, otherwise continue to look for.
The following code is my attempt, break does not seem to work.
Conremovedges:= proc(G::Graph,Paircrossedges)
local i,j,k,dedges;
for i from 1 to 2 do
for j from 1 to 2 do
for k from 1 to 2 do
dedges:={Paircrossedges[1][i],Paircrossedges[2][j],Paircrossedges[3][k]};
if EdgeConnectivity(DeleteEdge(G, dedges, inplace = false))=3 then
print(dedges);
break;
end if;
end do:
end do:
end do:
end proc:
Conremovedges(g1,Paircrossedges)
My idea is that as long as the edge set that meets the condition appears for the first time, it should stop. If none are satisfied, return "not found".
Another question：
The above is just my example. In fact, the graph I want to consider is more complicated. If there are 18 pairs of crossing edges, do I need to write 18th-order for-loops? This seems very troublesome. Is there an easier way? Maximum number of for loops is 2^18 that is equal to 262144, which is still acceptable.
Conremovedges:= proc(G::Graph,Paircrossedges)
local a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18,dedges;
for a1 from 1 to 2 do
for a2 from 1 to 2 do
for a3 from 1 to 2 do
for a4 from 1 to 2 do
for a5 from 1 to 2 do
for a6 from 1 to 2 do
for a7 from 1 to 2 do
for a8 from 1 to 2 do
for a9 from 1 to 2 do
for a10 from 1 to 2 do
for a11 from 1 to 2 do
for a12 from 1 to 2 do
for a13 from 1 to 2 do
for a14 from 1 to 2 do
for a15 from 1 to 2 do
for a16 from 1 to 2 do
for a17 from 1 to 2 do
for a18 from 1 to 2 do
dedges:={
Paircrossedges[1][a1],Paircrossedges[2][a2],Paircrossedges[3][a3],
Paircrossedges[4][a4],Paircrossedges[5][a5],Paircrossedges[6][a6],
Paircrossedges[7][a7],Paircrossedges[8][a8],Paircrossedges[9][a9],
Paircrossedges[10][a10],Paircrossedges[11][a11],Paircrossedges[12][a12],
Paircrossedges[13][a13],Paircrossedges[14][a14],Paircrossedges[15][a15],
Paircrossedges[16][a16],Paircrossedges[17][a17],Paircrossedges[18][a18]};
if EdgeConnectivity(DeleteEdge(G, dedges, inplace = false))=3 then
print(dedges);
break;
end if;
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end do:
end proc:
