dharr

Dr. David Harrington

8205 Reputation

22 Badges

20 years, 337 days
University of Victoria
Professor or university staff
Victoria, British Columbia, Canada

Social Networks and Content at Maplesoft.com

Maple Application Center
I am a retired professor of chemistry at the University of Victoria, BC, Canada. My research areas are electrochemistry and surface science. I have been a user of Maple since about 1990.

MaplePrimes Activity


These are answers submitted by dharr

Here's a small step in the right direction.

restart;

eq:=erf(x)=erf(Pi);

erf(x) = erf(Pi)

Define inverse function

inverf:=erf@@(-1);

erf@@(-1)

Apply it to both sides of the equation

map(inverf,eq);

x = Pi

solve(inverf(erf(x))=inverf(erf(Pi)),x);

Pi

But inverf isn't a linear function, so we don't expect anything more complicated to work.

inverf(erf(x)-erf(Pi))=inverf(0);

(erf@@(-1))(erf(x)-erf(Pi)) = (erf@@(-1))(0)

NULL

Download inverf.mw

The following parameters make it positive semidefinite:

My procedure was pretty ad-hoc, using Satisfy and just adding conditions until it worked.

positivedefinite.mw

@mmcdara - I think you needed C[1]<=0, but in 2015 it didn't lead to a solution even when I made that change, 2023 just gave one solution when solving the conditions. Since the matrix is symmetric, the discriminants of the quadratics have to be positive anyway, and the signs of the coefficents can be used to test for two positive roots. But I don't really see why your method gave a different result.


@sursumCorda I'd be suspicious of the deprecated linalg routine. All principal minors (of all sizes) need to non-neg, so perhaps systematically working through these would be a better method. 

Use datasetlabels = contents for this, but it isn't pretty.

The short answer is that there is no obvious way to do this. You can certainly make subsets and two-element subsets as you have described if you are using labeled structures (and exponential generating functions). But the OEIS series you gave is for unlabelled graphs, so I don't see how it could arise from labelled structures. The combstruct package takes a grammar and then enumerates for either labeled or unlabelled structures but not for a mixture.

I don't really understand the functorial composition. But as far as I can see, there doesn't seem to be a simple way that its generating function is related to the generating function of the operands, and the basis of the combstruct package is that the grammar translates directly to operations on generating functions.

(If your object is just to calculate the numbers in the OEIS series, that can be done through Polya counting and can be programmed in Maple.)

For consistency in the A and nA labels, use MathML for both, so set A:=`#mo(A)` (or use mi for both A and nA if you want italics). I also added padding=10 to StyleVertex so the lines don't touch the labels.

For the weight locations you could use GetVertexPositions and then programmatically adjust the locations for the colored edges to have the same y value as the corresponding uncolored ones, and then save with SetVertexPostions. But that is a lot of work, and for me the weights look OK already.

Arbrepondéré.mw

 

Perhaps could be done in fewer steps, but this works.

Note: I scaled the result arbitrarily to make it simpler, under the assumption that it is was intended to be equal to zero, but you can leave that out.

restart:

local gamma;

gamma

eqn := (diff(theta(x, z, t), x))^2*(K[1]-K[3])*cos(theta(x, z, t))*sin(theta(x, z, t))+(diff(theta(x, z, t), x))*((diff(theta(x, z, t), z))*(-K[1]*cos(2*theta(x, z, t))+K[3]*cos(2*theta(x, z, t)))-(1/2)*gamma[1]*(4*sin(theta(x, z, t))^2*u(x, z, t)+2*u(x, z, t)*cos(2*theta(x, z, t))))+(diff(theta(x, z, t), z))^2*(K[3]-K[1])*cos(theta(x, z, t))*sin(theta(x, z, t))-(1/2)*gamma[1]*(diff(theta(x, z, t), z))*(4*sin(theta(x, z, t))^2*v(x, z, t)+2*v(x, z, t)*cos(2*theta(x, z, t)))+(diff(theta(x, z, t), z, x))*(-2*K[1]+2*K[3])*cos(theta(x, z, t))*sin(theta(x, z, t))-(diff(u(x, z, t), z))*((1/2)*gamma[2]*cos(2*theta(x, z, t))+(1/2)*gamma[1]*(2*sin(theta(x, z, t))^2+cos(2*theta(x, z, t))))-(diff(v(x, z, t), x))*((1/2)*gamma[2]*cos(2*theta(x, z, t))+(1/2)*gamma[1]*(-2*sin(theta(x, z, t))^2-cos(2*theta(x, z, t))))-(1/2)*gamma[1]*(4*sin(theta(x, z, t))^2*(diff(theta(x, z, t), t))+2*(diff(theta(x, z, t), t))*cos(2*theta(x, z, t)))+((diff(u(x, z, t), x))*gamma[2]-(diff(v(x, z, t), z))*gamma[2])*cos(theta(x, z, t))*sin(theta(x, z, t))+f[2](theta(x, z, t))*(diff(theta(x, z, t), x, x))+f[1](theta(x, z, t))*(diff(theta(x, z, t), z, z));
 

(diff(theta(x, z, t), x))^2*(K[1]-K[3])*cos(theta(x, z, t))*sin(theta(x, z, t))+(diff(theta(x, z, t), x))*((diff(theta(x, z, t), z))*(-K[1]*cos(2*theta(x, z, t))+K[3]*cos(2*theta(x, z, t)))-(1/2)*gamma[1]*(4*sin(theta(x, z, t))^2*u(x, z, t)+2*u(x, z, t)*cos(2*theta(x, z, t))))+(diff(theta(x, z, t), z))^2*(K[3]-K[1])*cos(theta(x, z, t))*sin(theta(x, z, t))-(1/2)*gamma[1]*(diff(theta(x, z, t), z))*(4*sin(theta(x, z, t))^2*v(x, z, t)+2*v(x, z, t)*cos(2*theta(x, z, t)))+(diff(diff(theta(x, z, t), x), z))*(-2*K[1]+2*K[3])*cos(theta(x, z, t))*sin(theta(x, z, t))-(diff(u(x, z, t), z))*((1/2)*gamma[2]*cos(2*theta(x, z, t))+(1/2)*gamma[1]*(2*sin(theta(x, z, t))^2+cos(2*theta(x, z, t))))-(diff(v(x, z, t), x))*((1/2)*gamma[2]*cos(2*theta(x, z, t))+(1/2)*gamma[1]*(-2*sin(theta(x, z, t))^2-cos(2*theta(x, z, t))))-(1/2)*gamma[1]*(4*sin(theta(x, z, t))^2*(diff(theta(x, z, t), t))+2*(diff(theta(x, z, t), t))*cos(2*theta(x, z, t)))+((diff(u(x, z, t), x))*gamma[2]-(diff(v(x, z, t), z))*gamma[2])*cos(theta(x, z, t))*sin(theta(x, z, t))+f[2](theta(x, z, t))*(diff(diff(theta(x, z, t), x), x))+f[1](theta(x, z, t))*(diff(diff(theta(x, z, t), z), z))

Change the independent variables first

tr1:={t = T*tau,x = X*h, z = Z*h};
eqn2:=PDEtools:-dchange(tr1, eqn*T*h^2, [tau,X,Z],params=[T,h],simplify);

{t = T*tau, x = X*h, z = Z*h}

-2*T*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*(K[1]-K[3])*(diff(diff(theta(tau, X, Z), X), Z))+f[2](theta(tau, X, Z))*(diff(diff(theta(tau, X, Z), X), X))*T+f[1](theta(tau, X, Z))*(diff(diff(theta(tau, X, Z), Z), Z))*T+T*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*(K[1]-K[3])*(diff(theta(tau, X, Z), X))^2-(2*(cos(theta(tau, X, Z))^2-1/2)*(K[1]-K[3])*(diff(theta(tau, X, Z), Z))+u(tau, X, Z)*h*gamma[1])*T*(diff(theta(tau, X, Z), X))-T*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*(K[1]-K[3])*(diff(theta(tau, X, Z), Z))^2-(diff(theta(tau, X, Z), Z))*v(tau, X, Z)*T*h*gamma[1]+(-(cos(theta(tau, X, Z))^2*gamma[2]+(1/2)*gamma[1]-(1/2)*gamma[2])*T*(diff(u(tau, X, Z), Z))-T*(cos(theta(tau, X, Z))^2*gamma[2]-(1/2)*gamma[1]-(1/2)*gamma[2])*(diff(v(tau, X, Z), X))-(diff(theta(tau, X, Z), tau))*h*gamma[1]+T*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*gamma[2]*(diff(u(tau, X, Z), X)-(diff(v(tau, X, Z), Z))))*h

Now the dependent variables

tr2:={u(tau,X,Z) = xi*h^2*U(tau,X,Z)/alpha[4], v(tau,X,Z) = xi*h^2*V(tau,X,Z)/alpha[4]};
eqn3:=PDEtools:-dchange(tr2, eqn2*2*alpha[4], [U,V],params=[xi,h,alpha[4]],simplify);

{u(tau, X, Z) = xi*h^2*U(tau, X, Z)/alpha[4], v(tau, X, Z) = xi*h^2*V(tau, X, Z)/alpha[4]}

-4*T*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*alpha[4]*(K[1]-K[3])*(diff(diff(theta(tau, X, Z), X), Z))+2*f[2](theta(tau, X, Z))*(diff(diff(theta(tau, X, Z), X), X))*T*alpha[4]+2*f[1](theta(tau, X, Z))*(diff(diff(theta(tau, X, Z), Z), Z))*T*alpha[4]+2*T*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*alpha[4]*(K[1]-K[3])*(diff(theta(tau, X, Z), X))^2-2*T*(2*(cos(theta(tau, X, Z))^2-1/2)*alpha[4]*(K[1]-K[3])*(diff(theta(tau, X, Z), Z))+xi*h^3*U(tau, X, Z)*gamma[1])*(diff(theta(tau, X, Z), X))-2*T*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*alpha[4]*(K[1]-K[3])*(diff(theta(tau, X, Z), Z))^2-2*(diff(theta(tau, X, Z), Z))*xi*h^3*V(tau, X, Z)*T*gamma[1]-(T*h*xi*(2*cos(theta(tau, X, Z))^2*gamma[2]+gamma[1]-gamma[2])*(diff(U(tau, X, Z), Z))-T*h*xi*(-2*cos(theta(tau, X, Z))^2*gamma[2]+gamma[1]+gamma[2])*(diff(V(tau, X, Z), X))+2*gamma[1]*(diff(theta(tau, X, Z), tau))*alpha[4]-2*T*gamma[2]*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*h*xi*(diff(U(tau, X, Z), X)-(diff(V(tau, X, Z), Z))))*h^2

Now the rest, assuming f[1](theta(x, z, t)) was really intended as a function and not as multiplying by f[1] (same for f[2])

tr3 := {K[3] = K[1]*k[3], f[1](theta(x, z, t)) = K[1]*F[1](theta(x, z, t)), f[2](theta(x, z, t)) = K[1]*F[2](theta(x, z, t)), gamma[1] = mu*Gamma[1], gamma[2] = mu*Gamma[2]};

eqn4:=PDEtools:-dchange(tr3, eqn3, [k[3], F[1], F[2], Gamma[1], Gamma[2]],params=[K[1],mu],simplify);

{K[3] = K[1]*k[3], gamma[1] = mu*Gamma[1], gamma[2] = mu*Gamma[2], f[1](theta(x, z, t)) = K[1]*F[1](theta(x, z, t)), f[2](theta(x, z, t)) = K[1]*F[2](theta(x, z, t))}

4*T*alpha[4]*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*K[1]*(-1+k[3])*(diff(diff(theta(tau, X, Z), X), Z))+2*K[1]*F[2](theta(tau, X, Z))*(diff(diff(theta(tau, X, Z), X), X))*T*alpha[4]+2*K[1]*F[1](theta(tau, X, Z))*(diff(diff(theta(tau, X, Z), Z), Z))*T*alpha[4]-2*T*alpha[4]*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*K[1]*(-1+k[3])*(diff(theta(tau, X, Z), X))^2-2*(-2*(cos(theta(tau, X, Z))^2-1/2)*alpha[4]*K[1]*(-1+k[3])*(diff(theta(tau, X, Z), Z))+xi*h^3*U(tau, X, Z)*mu*Gamma[1])*T*(diff(theta(tau, X, Z), X))+2*T*alpha[4]*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*K[1]*(-1+k[3])*(diff(theta(tau, X, Z), Z))^2-2*(diff(theta(tau, X, Z), Z))*xi*h^3*V(tau, X, Z)*T*mu*Gamma[1]-mu*(T*h*xi*(2*cos(theta(tau, X, Z))^2*Gamma[2]+Gamma[1]-Gamma[2])*(diff(U(tau, X, Z), Z))-T*h*xi*(-2*cos(theta(tau, X, Z))^2*Gamma[2]+Gamma[1]+Gamma[2])*(diff(V(tau, X, Z), X))+2*Gamma[1]*(diff(theta(tau, X, Z), tau))*alpha[4]-2*T*Gamma[2]*cos(theta(tau, X, Z))*sin(theta(tau, X, Z))*h*xi*(diff(U(tau, X, Z), X)-(diff(V(tau, X, Z), Z))))*h^2

NULL

Download dchange.mw

Well, all but 2 are random...

restart;

with(LinearAlgebra):

Choose determinant required and Matrix size:

det:=9;n:=4;

9

4

Try to adjust 1,1 and 1,2 entries until it works. Values can be too high to look random - could play with the q values

imax:=10:
for i to imax do
  R:=RandomMatrix(n,n,generator=-5..5):
  R[1,1]:=a:
  R[1,2]:=b:
  eq:=isolve(Determinant(R)=det,q);
until eq<>NULL:
if i>imax then
  print(`too hard`);
else
  print(i);
  R:=eval(R,eval(eq,q=0));
  R:=eval(R,indets(R,name)=~0); # if there is an a or b left, set = 0
  Determinant(%);
end if;

1

Matrix(%id = 36893490371187920396)

9

NULL

Download GivenDet.mw

See also the thread here
How-To-Obtain-All-Cycles--In-A-Graph

restart

with(GraphTheory); with(Bits)

Using the adjacency matrix and zeons to count cycles.

See R. Schott and G.S. Staples, Complexity of counting cycles using zeons, Comp. Math. Appl. 62 (2011) 1828–1837, doi: 10.1016/j.camwa.2011.06.026

Zeons implemented with bitwise operations on Maple integers in the Bits package.

G := AddVertex(PathGraph(5, directed), [6, 7]); AddArc(G, {[1, 3], [3, 7], [4, 6], [6, 7], [7, 1]}); DrawGraph(G, layout = circle, size = [250, 250])

GRAPHLN(directed, unweighted, [1, 2, 3, 4, 5, 6, 7], Array(1..7, {(1) = {2}, (2) = {3}, (3) = {4}, (4) = {5}, (5) = {}, (6) = {}, (7) = {}}), `GRAPHLN/table/2`, 0)

n := NumberOfVertices(G)

7

Setting a bit in an integer.

SetBit := proc (p) Bits:-Join(convert(Vector(n, {p = 1}, fill = 0), list)) end proc; SetBits := proc () options operator, arrow; foldl(Bits:-Or, seq(SetBit(i), `in`(i, args))) end proc

Warning, (in SetBits) `i` is implicitly declared local

SetBit(3); String(%); q := SetBits(2, 3); String(%)

4

"001"

6

"011"

Going back

Decode := proc (p) options operator, arrow; zip(proc (x, y) options operator, arrow; if x = 1 then y end if end proc, Bits:-Split(p), [`$`(1 .. n)]) end proc; Decode(q)

[2, 3]

The algorithm starts with two versions of the adjacency matrix. Matrix B has the (i,j) entry as a coded version of i and j that is the beginning of a path or cycle.

Matrix A entry (i,j) has only the coded versionsof j; this is the vertex that will be added to the path at each step by evaluating B.A with a special rule for multiplication.

At any stage the list in entry (i,j) of B contains integers representing possible paths between i and j of a certain length k.

Adj := AdjacencyMatrix(G); A := Matrix(n, n, proc (i, j) options operator, arrow; if Adj[i, j] = 1 then SetBit(j) else 0 end if end proc); B := Matrix(n, n, proc (i, j) options operator, arrow; if Adj[i, j] = 1 then [Or(SetBit(i), SetBit(j))] else [] end if end proc); B, A

Matrix(%id = 36893490887404493628), Matrix(%id = 36893490887404491348)

Consider a list of two paths of length 2 from vertex 1 to vertex 3: 1-2-3 and 1-7-3 that would be in entry (1,3). Part of the next step would be trying to add vertex 7 to each of these paths.

b := [SetBits(1, 2, 3), SetBits(1, 7, 3)]; a := SetBit(7)

[7, 69]

64

The multiplication of two entries in the process of Matrix multiplication adds the a vertex to each of the possibilities in b. If it is a repeated vertex, then the possibility disappears. A duplicate is detected as the And of two values being nonzero. Adding the vertex is done by Or

And(7, 64); And(69, 64); Or(7, 64); Decode(%)

0

64

71

[1, 2, 3, 7]

Note that although we add the vertex, we lose information about the order. So this algorithm cannot output the cycles themselves. The following implements this multiplication.

map((x,y)-> if Bits:-And(x,y)=0 then Bits:-Or(x,y) else NULL end if,b,a);

[71]

A repeatng vertex isn't necessarily a cycle; only if the starting and ending vertex are the same. This will happen if we are multplying B[i,j]*A[j,p] with i=p, i.e., we are calculating a diagonal entry.

To prevent double counting, we only keep the cycle if the smallest vertex is i. The full multiplication rule is

mult:=(x,y)->if y = 0 or x=[] then []
             else
               map((u,w)-> if Bits:-And(u,w)=0 then
                              return Bits:-Or(u,w)
                           else
                              if i=p and i=Bits:-FirstNonzeroBit(u) + 1 then record_cycle end if;
                              return NULL;
                           end if,
                    x,y)
             end if:

Implement the Matrix multiplication with the above routine

MM:=proc(B,A) local C,i,j,p;
C:=Matrix(n,n):
for i to n do # rows of B diving down
  for p to n do # cols of A     
     C[i,p]:=[seq(mult(B[i,j],A[j,p])[],j=1..n)];  #Row(B,i).Column(A,p)
  end do
end do:
C
end proc:

C := MM(B, A)

Show := proc (M) options operator, arrow; map(proc (x) options operator, arrow; if 0 < nops(x) then map(Decode, x) else x end if end proc, M) end proc; Show(C)

Matrix(%id = 36893490887341852180)

Next one

B := C; C := MM(B, A); Show(C)

Matrix(%id = 36893490887341836396)

And again

B := C; C := MM(B, A); Show(C)

Matrix(%id = 36893490887253294844)

So here is a procedure to count cycles in a graph or digraph.

Output is a sparse table, indexed by the number of vertices in the cycles

Use add(eval(CycleCounts(G))) to find the total number of cycles.
This includes 2-cycles, one for each edge, so subtract the number of edges if you do not want 2-cycles in the total.

For undirected graphs, some authors count each cycle twice, one in each orientation, but here each cycle is counted only once.

CycleCounts:=proc(G::Graph)
  uses GraphTheory;
  local k,A,B,C,p,n,i,j,mult,cycles,SetBit;
  cycles:=table('sparse');
  n:=NumberOfVertices(G);
  SetBit := m-> Bits:-Join(convert(Vector(n, {m = 1}, 'fill' = 0), list));
  mult:=(x,y)->if y = 0 or x = [] then []
             else
               map((u,w)-> if Bits:-And(u,w)=0 then
                              return Bits:-Or(u,w)
                           else
                              if i=p and i=Bits:-FirstNonzeroBit(u) + 1 then cycles[k]++ end if;
                              return NULL;
                           end if,
                    x,y)
             end if;
  A:=Matrix(n,n, (i, j)-> if AdjacencyMatrix(G)[i, j] = 1 then SetBit(j) else 0 end if);
  B:= Matrix(n,n, (i, j)-> if AdjacencyMatrix(G)[i, j] = 1 then {Bits:-Or(SetBit(i),SetBit(j))} else [] end if);
  for k from 2 to n do
    C:=Matrix(n,n):
    for i to n do # rows of B diving down
      for p to n do # cols of A     
        C[i,p]:=[seq(mult(B[i,j],A[j,p])[],j=1..n)];  #Row(B,i).Column(A,p)
      end do
    end do;
    B:=C;
  end do;
  if not IsDirected(G) then # correct for double counting except for 2-cycles
        cycles:=map(i->i/2,cycles);
        if assigned(cycles[2]) then
            if cycles[2]=0 then # edgeless graphs
               evaln(cycles[2])
            else
               cycles[2]:=cycles[2]*2
            end if
        end if
  end if;
  eval(cycles);
end proc:
 

cycles := CycleCounts(G)

"for i,cyc in eval(cycles) do i,cyc end do;add(eval(cycles));"

3, 1

4, 1

5, 1

6, 1

4

"G3:=CompleteGraph(5);  cycles:=CycleCounts(G3):   for i,cyc in eval(cycles) do i,cyc end do;add(eval(cycles));    "

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5], Array(1..5, {(1) = {2, 3, 4, 5}, (2) = {1, 3, 4, 5}, (3) = {1, 2, 4, 5}, (4) = {1, 2, 3, 5}, (5) = {1, 2, 3, 4}}), `GRAPHLN/table/4`, 0)

2, 10

3, 10

4, 15

5, 12

47

G2 := RandomGraphs:-RandomGraph(15, .3)

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], Array(1..15, {(1) = {3, 8, 12}, (2) = {5, 7}, (3) = {1, 6, 13, 14}, (4) = {7, 11}, (5) = {2, 8, 14}, (6) = {3, 9, 15}, (7) = {2, 4, 8, 10, 12}, (8) = {1, 5, 7, 10, 11, 12, 13, 15}, (9) = {6, 14, 15}, (10) = {7, 8, 11, 15}, (11) = {4, 8, 10, 12, 15}, (12) = {1, 7, 8, 11, 14}, (13) = {3, 8, 15}, (14) = {3, 5, 9, 12, 15}, (15) = {6, 8, 9, 10, 11, 13, 14}}), `GRAPHLN/table/6`, 0)

cycles := CodeTools:-Usage(CycleCounts(G2))

memory used=138.66MiB, alloc change=0 bytes, cpu time=3.23s, real time=3.36s, gc time=156.25ms

"for i,cyc in eval(cycles) do i,cyc end do;add(eval(cycles)); "

2, 31

3, 11

4, 29

5, 58

6, 112

7, 215

9, 490

8, 349

11, 566

10, 579

13, 254

12, 450

15, 8

14, 78

3230

NULL

Download ZeonsCycleCounts.mw

Smarter than Tarjan, perhaps, but slower:

restart

with(GraphTheory)

Using the adjacency matrix and LinearAlgebra:-Generic to find cycles.

In this version, we use Arrays. In the modified adjacency matrix we just use jand not {[i, j]}.

G := AddVertex(PathGraph(5), [6, 7]); AddEdge(G, {{1, 3}, {1, 7}, {3, 7}, {4, 6}, {6, 7}}); DrawGraph(G, layout = circle, size = [250, 250])

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7], Array(1..7, {(1) = {2}, (2) = {1, 3}, (3) = {2, 4}, (4) = {3, 5}, (5) = {4}, (6) = {}, (7) = {}}), `GRAPHLN/table/2`, 0)

n := NumberOfVertices(G)

7

Adj := AdjacencyMatrix(G); A := Matrix(n, n, proc (i, j) options operator, arrow; if Adj[i, j] = 1 then j else 0 end if end proc); B2 := Matrix(n, n, proc (i, j) options operator, arrow; if Adj[i, j] = 1 then {Array([i, j])} else {} end if end proc, datatype = set); B2, A

Matrix(%id = 36893489640244560108), Matrix(%id = 36893489640244559988)

Now we need to modify how we do matrix multiplication, but Maple has the LinearAlgebra:-Generic package to do this. We can redefine addition and multiplication to operate correctly on the sets of sets.

Consider two sets of sets of vertices for walks. WE ASSUME THE SECOND ONE HAS ONLY ONE VERTEX.

a := {Array([7]), Array([1, 3, 4]), Array([2, 6, 7])}; b := 4

{Array(%id = 36893489716560989828), Array(%id = 36893489716560989948), Array(%id = 36893489716560990068)}

4

Addition is just combining the possibilities, and set union will do this. And addition of "zero" should add no possibilities, so we take {} as zero.

`union`(a, {Array([b])}); `union`(a, {})

{Vector(1, {(1) = 4}), Vector(1, {(1) = 7}), Vector[row](3, {(1) = 1, (2) = 3, (3) = 4}), Vector[row](3, {(1) = 2, (2) = 6, (3) = 7})}

{Array(%id = 36893489716560989828), Array(%id = 36893489716560989948), Array(%id = 36893489716560990068)}

Multiplication is adjoining the extra vertex. But if the new is the same as an existing one we have intersected ourself, but not necessarily made a simple cycle. So we want to stop adding vertices by making the matrix entry {}. We can identify it as a cycle if it intersects the first vertex.

map((x,y)->if y in x then NULL else (Array(x),=y) end if,a,b);

{Vector[row](2, {(1) = 7, (2) = 4}), Vector[row](4, {(1) = 2, (2) = 6, (3) = 7, (4) = 4})}

The unit for multiplication should leave the set of sets unchanged, so {Array([])} can be used. (but never called)

map((x,y)->if y in x then NULL else (Array(x),=y) end if,{Array([])},b);
map((x,y)->if y in x then NULL else (Array(x),=y) end if,a,{Array([])}[]); #needs special case

{Vector(1, {(1) = 4})}

{Array(%id = 36893489716560962252), Array(%id = 36893489716560962492), Array(%id = 36893489716560962732)}

And we should check that zero multiplied by a is zero

map((x,y)->if y in x then NULL else (Array(x),=y) end if,{},b);
map((x,y)->if y in x then NULL else (Array(x),=y) end if,a,{}); #treat as special case

{}

{Array(%id = 36893489716560959956), Array(%id = 36893489716560960196), Array(%id = 36893489716560960436)}

Define these operations for the LinearAlgebraGeneric package:

cycles := table(); m := 0; F[`=`] := `=`; F[`/`] := `/`; F[`0`] := {}; F[`1`] := 1; F[`+`] := `union`

F[`*`]:=(x, y) -> if y = 0 or y={} or x = {} then {}
                    elif y = {Array([])} then x
                    else map(proc(u, w);
                               if w in u then
                                  if w = u[1] and w = min(u) then cycles[k][u] := NULL end if;                                                     return NULL
                               else
                                  return (Array(u),=w)
                               end if;
                             end proc, x, y)
                    end if:

Warning, (in anonymous procedure within F[*]) `cycles` is implicitly declared local

B3 := LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B2, A)

Matrix(%id = 36893489716538042956)

B4 := LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B3, A)

B5 := LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B4, A)

B6 := LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B5, A)

B7 := LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B6, A)

B8 := LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B7, A)

Matrix(%id = 36893489716513642604)

DrawGraph(G, size = [200, 200], layout = circle)

So here is a procedure for the cycles in a graph - each cycle appears twice.

Cycles:=proc(G::Graph)
  uses GraphTheory;
  local x,y,k,u,w,A,B,F,n,cycles;
  #if IsDirected(G) then error "graph must be undirected" end if;
  cycles:=table();
  F[`=`]:=`=`:F[`/`]:=`/`: # not required but have to be specified
  F[`0`]:={}:
  F[`1`]:={Array([])}: # never used
  F[`+`]:=`union`:     # can get arguments in any order
  F[`*`]:=(x, y)       # x from left Matrix, y from right Matrix
                 -> if y = 0 or x = {} then {}
                    #elif y = {Array([])} then x
                    else map(proc(u, w);
                               if w in u then
                                  if w = u[1] and w = min(u) then cycles[k][u] := NULL end if;
                                  return NULL
                               else
                                  return (Array(u),=w)
                               end if;
                             end proc, x, y)
                    end if;
  n:=NumberOfVertices(G);
  A:=Matrix(n,n, (i, j)-> if AdjacencyMatrix(G)[i, j] = 1 then j else 0 end if);
  B:= Matrix(n,n, (i, j)-> if AdjacencyMatrix(G)[i, j] = 1 then {Array([i,j])} else {} end if);
  for k from 2 to n do
    B:=LinearAlgebra:-Generic:-MatrixMatrixMultiply[F](B,A);
  end do;
  cycles:=map({indices},cycles,'nolist');
  #cycles[2]:=evaln(cycles[2]); # if don't include 2-cycles
  eval(cycles);
end proc:

cycles := Cycles(G)

"for i,cyc in eval(cycles) do i,cyc end do;"

2, {Vector[row](2, {(1) = 6, (2) = 7}), Vector[row](2, {(1) = 4, (2) = 5}), Vector[row](2, {(1) = 4, (2) = 6}), Vector[row](2, {(1) = 3, (2) = 4}), Vector[row](2, {(1) = 3, (2) = 7}), Vector[row](2, {(1) = 2, (2) = 3}), Vector[row](2, {(1) = 1, (2) = 2}), Vector[row](2, {(1) = 1, (2) = 3}), Vector[row](2, {(1) = 1, (2) = 7})}

3, {Vector[row](3, {(1) = 1, (2) = 3, (3) = 7}), Vector[row](3, {(1) = 1, (2) = 3, (3) = 2}), Vector[row](3, {(1) = 1, (2) = 2, (3) = 3}), Vector[row](3, {(1) = 1, (2) = 7, (3) = 3})}

4, {Vector[row](4, {(1) = 3, (2) = 7, (3) = 6, (4) = 4}), Vector[row](4, {(1) = 3, (2) = 4, (3) = 6, (4) = 7}), Vector[row](4, {(1) = 1, (2) = 2, (3) = 3, (4) = 7}), Vector[row](4, {(1) = 1, (2) = 7, (3) = 3, (4) = 2})}

5, {Vector[row](5, {(1) = 1, (2) = 3, (3) = 4, (4) = 6, (5) = 7}), Vector[row](5, {(1) = 1, (2) = 7, (3) = 6, (4) = 4, (5) = 3})}

6, {Array(%id = 36893489717559867020), Array(%id = 36893489717559868220)}

numelems(cycles)

5

add(nops(i), `in`(i, eval(cycles)))

21

G2 := RandomGraphs:-RandomGraph(15, .3, seed = 27)

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], Array(1..15, {(1) = {3, 8, 12}, (2) = {5, 7}, (3) = {1, 6, 13, 14}, (4) = {7, 11}, (5) = {2, 8, 14}, (6) = {3, 9, 15}, (7) = {2, 4, 8, 10, 12}, (8) = {1, 5, 7, 10, 11, 12, 13, 15}, (9) = {6, 14, 15}, (10) = {7, 8, 11, 15}, (11) = {4, 8, 10, 12, 15}, (12) = {1, 7, 8, 11, 14}, (13) = {3, 8, 15}, (14) = {3, 5, 9, 12, 15}, (15) = {6, 8, 9, 10, 11, 13, 14}}), `GRAPHLN/table/7`, 0)

cycles := CodeTools:-Usage(Cycles(G2))

memory used=0.57GiB, alloc change=-32.00MiB, cpu time=5.88s, real time=4.94s, gc time=1.89s

add(nops(i), `in`(i, eval(cycles)))

6429

sort([indices(cycles, 'nolist')])

[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

NULL

Download GenericCyclesArraysVerticesOnly2.mw

I looked into this a while ago, and found Tarjan's backtracking algorithm is quite efficient, implementing the stack with Maple's DEQueue (not using the double ended feature). I just implemented it as stated; it may be able to be improved (perhaps the stack clearing). This doesn't use the cycle basis though.

Tarjan's algorithm for finding cycles. R. Tarjan,  Enumeration of the Elementary Circuits of a Directed Graph, SIAM J. Comput. 2 (1973)  211.   doi: 10.1137/0202017

Procedure Tarjan (in startup code) accepts a Graph and outputs a table with all cycles of a graph, indexed by the size of the cycles.
For an undirected graph each cycle except the 2-cycles appears twice, once in each orientation (clockwise or counterclockwise).

Cycles of a given size are in sets, with each cycle gives as an ordered list of vertices in the cycle, with the vertices numbered 1,..n, in the same order as Vertices(G). The lowest numbered vertex is first in the cycle.

 

For counting cycles without producing the cycles themselves use procedure TarjanCounts, which produces a table indexed by the cycle sizes giving counts of cycles of that size. This time, each cycle counts once; there is no double counting for undirected graphs.

restart;

with(GraphTheory):

G := AddVertex(PathGraph(5, directed), [6, 7]):
AddArc(G, {[1, 3], [3, 7], [4, 6], [6, 7], [7, 1],[4,7]});
DrawGraph(G, layout = circle, size = [250, 250]);

GRAPHLN(directed, unweighted, [1, 2, 3, 4, 5, 6, 7], Array(1..7, {(1) = {2, 3}, (2) = {3}, (3) = {4, 7}, (4) = {5, 6, 7}, (5) = {}, (6) = {7}, (7) = {1}}), `GRAPHLN/table/2`, 0)

Cycles broken down by lengths.

cycles:=Tarjan(G):

for i,cycle in eval(cycles) do
  i, cycle;
end do;

3, {[1, 3, 7]}

4, {[1, 2, 3, 7], [1, 3, 4, 7]}

5, {[1, 2, 3, 4, 7], [1, 3, 4, 6, 7]}

6, {[1, 2, 3, 4, 6, 7]}

Total number of cycles

add(map(nops,cycles));

6

counts:=TarjanCounts(G):
for i,cycle in eval(counts) do
  i, cycle;
end do;
add(eval(counts));

3, 1

4, 2

5, 2

6, 1

6

G2 := RandomGraphs:-RandomGraph(15, .3, seed = 27)

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15], Array(1..15, {(1) = {3, 8, 12}, (2) = {5, 7}, (3) = {1, 6, 13, 14}, (4) = {7, 11}, (5) = {2, 8, 14}, (6) = {3, 9, 15}, (7) = {2, 4, 8, 10, 12}, (8) = {1, 5, 7, 10, 11, 12, 13, 15}, (9) = {6, 14, 15}, (10) = {7, 8, 11, 15}, (11) = {4, 8, 10, 12, 15}, (12) = {1, 7, 8, 11, 14}, (13) = {3, 8, 15}, (14) = {3, 5, 9, 12, 15}, (15) = {6, 8, 9, 10, 11, 13, 14}}), `GRAPHLN/table/5`, 0)

cycles := CodeTools:-Usage(Tarjan(G2))

memory used=90.10MiB, alloc change=32.00MiB, cpu time=1.81s, real time=1.82s, gc time=125.00ms

Numbers with different lengths.

"for i,cyc in eval(cycles) do i,nops(cyc) end do;add(eval(map(nops,cycles))); "

2, 31

3, 22

4, 58

5, 116

6, 224

7, 430

9, 980

8, 698

11, 1132

10, 1158

13, 508

12, 900

15, 16

14, 156

6429

The 16 cycles of length 15

cycles[15]

{[1, 3, 6, 9, 14, 5, 2, 7, 4, 11, 10, 15, 13, 8, 12], [1, 3, 6, 9, 15, 13, 8, 10, 11, 4, 7, 2, 5, 14, 12], [1, 3, 13, 8, 5, 2, 7, 4, 11, 10, 15, 6, 9, 14, 12], [1, 3, 13, 8, 10, 15, 6, 9, 14, 5, 2, 7, 4, 11, 12], [1, 3, 13, 15, 6, 9, 14, 5, 2, 7, 4, 11, 10, 8, 12], [1, 8, 5, 2, 7, 4, 11, 10, 15, 13, 3, 6, 9, 14, 12], [1, 8, 10, 15, 13, 3, 6, 9, 14, 5, 2, 7, 4, 11, 12], [1, 8, 13, 3, 6, 9, 15, 10, 11, 4, 7, 2, 5, 14, 12], [1, 12, 8, 10, 11, 4, 7, 2, 5, 14, 9, 6, 15, 13, 3], [1, 12, 8, 13, 15, 10, 11, 4, 7, 2, 5, 14, 9, 6, 3], [1, 12, 11, 4, 7, 2, 5, 14, 9, 6, 3, 13, 15, 10, 8], [1, 12, 11, 4, 7, 2, 5, 14, 9, 6, 15, 10, 8, 13, 3], [1, 12, 14, 5, 2, 7, 4, 11, 10, 8, 13, 15, 9, 6, 3], [1, 12, 14, 5, 2, 7, 4, 11, 10, 15, 9, 6, 3, 13, 8], [1, 12, 14, 9, 6, 3, 13, 15, 10, 11, 4, 7, 2, 5, 8], [1, 12, 14, 9, 6, 15, 10, 11, 4, 7, 2, 5, 8, 13, 3]}

This version just counts cycles, and doesn't output them.

counts := CodeTools:-Usage(TarjanCounts(G2))

memory used=53.73MiB, alloc change=0 bytes, cpu time=812.00ms, real time=815.00ms, gc time=0ns

"for i,cycle in eval(counts) do    i, cycle;  end do;  add(eval(counts));  "

2, 31

3, 11

4, 29

5, 58

6, 112

7, 215

9, 490

8, 349

11, 566

10, 579

13, 254

12, 450

15, 8

14, 78

3230

NULL

Download Tarjan.mw

Code in startup code reproduced here (version that just counts is also there). 

# Tarjan outputs a table with all cycles of a graph, indexed by the size of the cycles
# for an undirected graph each cycle except the 2-cycles appears twice, once for each orientation.
Tarjan:=proc(G::GRAPHLN);
  local V,AA,backtrack,cycles,marked_stack,point_stack,mark,A,u,i;
#  
  backtrack:=proc(s,v)
    local f,u,w,g;
    f:=false;
    push_back(point_stack,v);
    mark[v]:=true;
    push_back(marked_stack,v);
    for w in A[v] do
      if w<s then
        A[v]:=A[v] minus {w};
      elif w=s then
        cycles[numelems(point_stack)][convert(point_stack,list)]:=NULL; #record cycle
        f:=true;
      elif not mark[w] then
        g:=procname(s,w);
        f:=f or g;
      end if; 
    end do;
    if f then
      while back(marked_stack)<>v do
        u:=pop_back(marked_stack);
        mark[u]:=false
      end do;
      pop_back(marked_stack);
      mark[v]:=false;
    end if;
    pop_back(point_stack);
    return f;
  end proc:
#
  V:=GraphTheory:-NumberOfVertices(G):
  AA:=op(4,G):
  cycles:=table():
  marked_stack:=DEQueue():
  point_stack:=DEQueue():
  mark:=Vector(V,'fill'=false): 
  for i to V do
    A:=copy(AA);
    backtrack(i,i);
    while not empty(marked_stack) do
      u:=pop_back(marked_stack);
      mark[u]:=false;
    end do;
  end do;
  map({indices},cycles,'nolist');
end proc;

 

restart;

fun:=(2*(x+y+z)*(sqrt(y*z*(z+x)*(x+y))/(z+2*x+y\
)+sqrt(z*x*(x+y)*(y+z))/(x+2*y+z)+sqrt(x*y*(y+z)*(z+x))/(y\
+2*z+x))-(9*x*y*z/(x+y+z)+2*(y*z+z*x+x*y)))/(sqrt(x*y*z/(x+y+z))*(x+y+z-sqrt(27*x*y*z/(x+y+z))));

(2*(x+y+z)*((y*z*(z+x)*(x+y))^(1/2)/(z+2*x+y)+(z*x*(x+y)*(y+z))^(1/2)/(x+2*y+z)+(x*y*(y+z)*(z+x))^(1/2)/(y+2*z+x))-9*x*y*z/(x+y+z)-2*x*y-2*z*x-2*y*z)/((x*y*z/(x+y+z))^(1/2)*(x+y+z-3*3^(1/2)*(x*y*z/(x+y+z))^(1/2)))

Apply a mix of the strategies of @mmcdara and @Axel Vogt
If we scale each variable by a, we do not change the value of fun.

simplify(eval(fun,{x=a*x,y=a*y,z=a*z})-fun) assuming a>0;

0

So we can arbitrarily set x=1, and reduce it to a to two-variable problem a la @mmcdara 

f2:=eval(fun,x=1);

(2*(1+y+z)*((y*z*(z+1)*(1+y))^(1/2)/(z+2+y)+(z*(1+y)*(y+z))^(1/2)/(1+2*y+z)+(y*(y+z)*(z+1))^(1/2)/(y+2*z+1))-9*y*z/(1+y+z)-2*y-2*z-2*y*z)/((y*z/(1+y+z))^(1/2)*(1+y+z-3*3^(1/2)*(y*z/(1+y+z))^(1/2)))

As @Axel Vogt noted if we take z=1/y we achieve the alleged maximim at y=0 and y=infinity, suggesting we want y=0 and z=infinity or vice versa

f3:=eval(f2,z=1/y):plot(f3,y=0..infinity);

limit(f3,y=0,right);limit(f3,y=infinity);

3

3

So we take this as the initialpoint and see how well we will do

Optimization:-Maximize(f2, assume = nonnegative, initialpoint=[y=0,z=infinity]);

Error, (in Optimization:-NLPSolve) no improved point could be found

Well if we trust this, we have hit the jackpot. But let's try some values slightly off. The large z is unchanged

Optimization:-Maximize(f2, assume = nonnegative, initialpoint=[y=0.011,z=1e99]);

[2.99992758143340721, [y = HFloat(5.245208740234373e-9), z = HFloat(1.0e99)]]

Any smaller y leads to

Optimization:-Maximize(f2, assume = nonnegative, initialpoint=[y=0.010,z=1e99]);

Error, (in Optimization:-NLPSolve) no improved point could be found

This calculation is apparently done with the NAG routines (From the package overview help:  "The package takes advantage of built-in library routines provided by the Numerical Algorithms Group (NAG)"), which I took to mean it was done at hardware precision. Therefore I was expecting it to not to improve once Digits was higher than the evalhf(Digits) value (here 15). But it does seem possible now we are close to the right answer:

interface(warnlevel=0): #suppress "Warning, undefined value encountered"
Digits:=200:Optimization:-Maximize(f2, assume = nonnegative, initialpoint=[y=0.011,z=1e99]);

[2.9999999999999999999999999999999999999999999247516555104709641542678761099816238690915654672583419578491297268017405799331360347132599488479389709595136496067605126924167379345836314102243395093179334, [y = 0.5662313348414834814254640516705528534865083659384528553994345057261954945412478787036056872028862040374424169170634373413651693528242473844175580875428522750403316577543152997612261773087874496261451e-86, z = 0.1e100]]

NULL

Download maximize.mw

restart

with(LinearAlgebra)

eq := a+b+c = n*x; eq2 := a+3*b+c = n*y; eq3 := a+b+5*c = n*z; eq4 := 4*a+8*b = n*w

a+b+c = n*x

a+3*b+c = n*y

a+b+5*c = n*z

4*a+8*b = n*w

A, b := GenerateMatrix([eq, eq2, eq3, eq4], [a, b, c, n])

Matrix(%id = 36893489914357921060), Vector[column](%id = 36893489914357920940)

Consider the case used by @tomleslie

A1 := eval(A, [x = 1, y = 1, z = 6, w = -1]); Rank(%)

Matrix(%id = 36893489914357910812)

3

Since the Rank is 3, there is an infinite set of one-parameter solutions, as @tomleslie found from isolve, and they are integer

LinearSolve(A1, b)

Vector[column](%id = 36893489914357963100)

If the rank is 4 then the only solution will be a=b=c=n=0., which doesn't have n positive.

So the only sets of {w,x,y,z} that have solutions (integer or otherwise) will be those that make the last column a linear combination of the other 3 columns. The solutions are then the coefficients of the linear combination. For example we can add the columns

add(Column(A, 1 .. 3)); Equate(`<,>`(x, y, z, w), %); A2 := eval(A, %)

Vector(4, {(1) = 3, (2) = 5, (3) = 7, (4) = 12})

[x = 3, y = 5, z = 7, w = 12]

Matrix(%id = 36893489914345976044)

and so the solution is (by construction) {a=b=c=n=1} or any multiple of this.

LinearSolve(A2, b)

Vector[column](%id = 36893489914345981340)

NULL

Download LinearSystem.mw

Here's one way.

restart

a := 8*sqrt(2)*cis((1/4)*Pi); b := 8*sqrt(2)*cis(9*Pi*(1/4))

8*2^(1/2)*cis((1/4)*Pi)

8*2^(1/2)*cis((9/4)*Pi)

eval(a-b, cis = (proc (theta) options operator, arrow; cos(theta)+I*sin(theta) end proc))

0

NULL

 

Download cis.mw

Here are two suggestions.

restart

timestep := `<,>`(seq(1 .. 100))

fn := map(proc (t) options operator, arrow; t^2 end proc, timestep)

u := map(proc (t) options operator, arrow; Heaviside(t-30) end proc, timestep)

plot(timestep, `~`[`*`](u, fn), style = point)

uf := map(proc (t) options operator, arrow; piecewise(t < 30, 0, t^2) end proc, timestep)

plot(timestep, uf, style = point)

NULL

Download Heaviside.mw

For me (2023.0, Windows 10), the second one hangs, but if I use the stop icon (after 250 s) it quickly ends and prints "done", and then I can continue to use Maple as normally.

First 28 29 30 31 32 33 34 Last Page 30 of 81