lcz

How to quickly convert this adjacency li...

Asked: lcz 994 Product: Maple

March 29 2021

2 4

Today I got some useful graph datas in the form of adjacency list like following:

1: 2 3 4 5
2: 1 5 6 7
3: 1 7 8 9
4: 1 9 10 11
5: 1 11 12 2
6: 2 12 13 7
7: 2 6 8 3
8: 3 7 13 14
9: 3 14 10 4
10: 4 9 15 16
11: 4 16 17 5
12: 5 17 18 6
13: 6 18 19 8
14: 8 19 15 9
15: 10 14 20 21
16: 10 21 22 11
17: 11 22 23 12
18: 12 23 24 13
19: 13 24 20 14
20: 15 19 25 21
21: 15 20 22 16
22: 16 21 25 17
23: 17 25 24 18
24: 18 23 25 19
25: 20 24 23 22

I originally planned to enter them in maple one by one manually,

with(GraphTheory):
G:=Graph({{1,2},{1,3},{1,4},{1,5},{2,5},{2,6},{2,7},{3,7},{3,8},{3,9},{4,9},{4,10},{4,11},{5,11},{5,12},{6,7},{6,12},{6,13},{7,8},{8, 7}, {8,13},{8,14},{9,14},{9,10},{10,15},{10,16},{11,16},{11,17},{12,17},{12,18},{13,18},{13,19},{14,19},{14,15},{15,20},{15,21},{16,21},{16,22},{17,22},{17,23},{10,9},{10,15},{10,16},{11,16},{11,17},{12,17},{12,18},{13,18},{13,19},{14,19},{14,15},{15,20},{15,20},{15,21},{16,21},{16,22},{17,22},{17,23},{18,23},{18,24},{19,20},{19,24},{20,21},{20,25},{21,22},
{22,25},{23,24},{23,25},{24,25}})

but I will consider a lot of graph datas, I don’t know if there is a program that can help, Thanks advance!

Is there an efficient way to test wheth...

Asked: lcz 994

March 25 2021

0 0

I asked before how to determine whether a graph is outerplanar graph. vv and Carl Love provided very good guidance.

https://www.mapleprimes.com/questions/229128--How-To-Determine-If-A-Graph-Is-Outerplanar

Today I tried to use the previous code to further determine whether a plane graph is maximal outerplanar graph.

A maximal outerplanar graph is an outerplanar graph that cannot have any additional edges added to it while preserving outerplanarity.

IsOuterplanar:= proc(G::Graph)
uses GT= GraphTheory;
GT:-IsPlanar(GT:-GraphJoin(G, GT:-PathGraph(1)))
end proc:

IsmaximalOuterplanar:= proc(G::Graph)
uses GT= GraphTheory:
local glist, Outerplanartest:
glist:= map[2](GT:-AddEdge,G,GT:-Edges(GT:-GraphComplement(G)),inplace = false ):
Outerplanartest:=IsOuterplanar~(glist):
if evalb(true in Outerplanartest) then
return false:
else
return true:
fi:
end proc:

I feel that the above adding edges in programs is a bit inefficient.

So I wonder if there is a better way. Then I want to start from property of this graph class.

Some Properties:

Every maximal outerplanar graph with n vertices has exactly 2n − 3 edges.
A graph on n (>=3) vertices is maximal outerplanar graph if and if every bounded face of a maximal outerplanar graph is a triangle and boundary of unbounded face is Hamiltonian cycle.

I noticed the second one. I don’t know if it can be achieved through programming.

I want to get some information about the degree sequence of the face with the help of the dual graph . But I know dual graph not unique since there are different plane embeddings for not 3 connected planar graphs.

Or is there a more efficient way？

Why doesn't break work?...

Asked: lcz 994 Product: Maple 2021

March 19 2021

2 4

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:

How to convert real roots into expressi...

Asked: lcz 994 Product: Maple 2020

March 18 2021

3 3

I easily found the roots of the following equations,

s:=solve(x^3+x^2-2*x-1,x)

I accidentally discovered that 2*cos((2*Pi)/7) is also the root of this equation.

simplify(eval(x^3+x^2-2*x-1,x=2*cos((2*Pi)/7)))

0

It’s easy to know that 2*cos((2*Pi)/7) is equivalent to the third root found above

s1:=fsolve(x^3+x^2-2*x-1,x);
2*cos((2*Pi)/7.)

s := -1.801937736, -0.4450418679, 1.246979604

1.246979604

Maybe I don’t like the use of imaginary units, and I prefer 2*cos((2*Pi)/7) .

In the case that I don’t know that 2*cos((2*Pi)/7) is the solution of the equation, can I make a certain transformation without using the imaginary unit to represent the real number. For example, trigonometric functions, exponential functions, etc.

I tried to use the following functions, all failed.

s:=solve(x^3+x^2-2*x-1,x);
convert(s[3],cos);
identify(s[3])

What is interesting is the following phenomenon. Even if Zeta function does not look great:

s1:=fsolve(x^3+x^2-2*x-1,x):
identify(s1[3])

For this example, can all roots be transformed into trigonometric expressions by maple.

Can we create more graphs with this fun...

Asked: lcz 994 Product: Maple 2021

March 16 2021

1 2

I get the degree sequence of a graph, I want to create more graphs, but maple seems to only get the only graph.

Is there a good way to get more, a foolish dream, can we get all the graphs that satisfy this degree sequence condition?

with(GraphTheory):
L:=[7$1..22,6]:
IsGraphicSequence(L):
G := SequenceGraph(L):
DrawGraph(%)

E-Mail Address:
Password:
Remember Me:	Automatically sign in on future visits

E-Mail Address:
Password:
Remember Me:	Automatically sign in on future visits

Ask a Question

Create a Post

994 Reputation

11 Badges

MaplePrimes Activity

These are questions asked by lcz