> 

> 

Consider the following graph. We want to find, for a given vertex , the shortest walk that visits all vertices and returns to . A walk traverses the graph along the edges, and repeating an edge is allowed (as distinct from a path, in which an edge can be used only once).
> 

> 

> 

As is well known, the () entry of gives the number of walks of length between vertices and . The labelled adjacency matrix shows the actual walks.
> 

For example, the (3,3) entry of has 3 terms, one for each walk of length 2 that starts and ends at vertex 3.. The factors in a term give the edges visited.
So the algorithm to find the shortest walk is to raise to successively higher powers until one of the terms in the diagonal entry for the vertex of interest has indices for all the vertices.
> 

The expressions for higher powers get very large quickly, so an algorithm that only retains the sets of vertices in each term as a set of sets will use less storage space. So we can consider the following modified labelled adjacency matrix.
> 

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 set of sets of vertices for walks.
> 

Addition is just combining the possibilities. And addition of "zero" should add no possibilities, so we take {} as zero.
> 

Multiplication is just combining all pairs by union. Notice here that {7} union {1,2} and {1,2} union {7} give the same result, but that we do not get duplicates in the set.
> 

The unit for multiplication should leave the set of sets unchanged, so {{}} can be used
> 

Define these operations for the LinearAlgebraGeneric package:
> 

Warning, (in F[*]) `j` is implicitly declared local
Warning, (in F[*]) `i` is implicitly declared local
Compare with . We have lost information about the details of the walks except for the vertices visited.
> 

So here is a procedure for finding the length of the shortest returning walk.
> 
WalkLength:=proc(G::Graph,v)
uses GraphTheory;
local x,y,i,j,vv,A,B,F,n,vertset;
if IsDirected(G) then error "graph must be undirected" end if;
if not member(v,Vertices(G),'vv') then error "vertex not in graph" end if;
if not IsConnected(G) then return infinity end if;
F[`=`]:=`=`:F[`/`]:=`/`: # not required but have to be specified
F[`0`]:={}:
F[`1`]:={{}}:
F[`+`]:=`union`;
F[`*`]:=(x,y)>{seq(seq(i union j, i in x), j in y)};
n:=NumberOfVertices(G);
vertset:={$(1..n)};
A:=Matrix(n,n, (i, j)> if AdjacencyMatrix(G)[i, j] = 1 then {{i, j}} else {} end if);
B:=copy(A);
for i from 2 do
B:=LinearAlgebra:Generic:MatrixMatrixMultiply[F](B,A);
until vertset in B[vv,vv];
i;
end proc:

> 

> 

