Re: Hamiltonian circuits
- To: mathgroup at smc.vnet.net
- Subject: [mg67865] Re: [mg67774] Hamiltonian circuits
- From: leigh pascoe <leigh at cephb.fr>
- Date: Tue, 11 Jul 2006 05:58:27 -0400 (EDT)
- References: <200607071112.HAA27528@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Frank Brand wrote:
> Dear newsgroup members,
>
> I'm concerned with a severe problem related to look for closed cycles in
> graphs. Nameley, I'm searching for Hamiltonian cycles / circuits in a
> graph, but ALL cycles of different length up to n (n = # of vertices
> given). An example may help to understand what I'm looking for.
>
> Given the adjacency matrix
>
>
> AdjMatrix = {{0, 1, 0,
> 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0,
> 1, 0,
> 0, 0, 0, 0, 0}, {0, 1, 0, 0,
> 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 1,
> 1, 0,
> 0, 0, 0, 0}, {0, 0, 0, 0,
> 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0,
> 0, 0,
> 1, 0, 0, 0}, {1, 0, 0, 1,
> 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0,
> 0, 0, 0, 0}, {0, 1, 0, 0,
> 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 1, 0, 0, 1, 0,
> 0, 0,
> 0, 0, 0, 0}, {0, 0, 0, 0,
> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 0,
> 0, 0,
> 0, 0, 0, 0}, {1, 0, 0, 0,
> 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0,
> 0, 0, 0, 0}, {0, 0, 0, 0,
> 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
> 0, 0,
> 0, 0, 0, 0}}
>
>
> in this particular example the circuits are:
>
>
> AllCircuits = {{1, 7, 1}, {1, 10, 1}, {4, 7, 4}, {6, 13, 6}, {1, 2, 7, 1}, {
> 1, 2, 10, 1}, {2, 7, 4, 2}, {2, 7, 6, 2}, {2, 7, 9, 2}, {2, 10, 6,
> 2}, {2,
> 10, 9, 2}, {3, 7, 6, 3}, {3, 10, 6, 3}, {6, 13, 10, 6}, {
> 1, 7, 4, 10, 1}, {1, 7, 6, 13, 1}, {1, 10, 6, 13, 1}, {
> 2, 7, 6, 3, 2}, {2, 10, 6, 3, 2}, {1, 2, 7, 4, 10, 1}, {1, 2,
> 7, 6, 13, 1}, {1, 2, 10, 6,
> 13, 1}, {1, 7, 4, 2, 10, 1}, {1, 7, 6, 2, 10, 1}, {1, 7, 6,
> 3, 10, 1}, {1, 7, 6, 13, 10, 1}, {1, 7, 9, 2, 10, 1}, {1, 10, 6, 2, 7,
> 1}, {1, 10, 6, 3, 7, 1}, {1, 10, 9, 2, 7, 1}, {2, 7, 4, 10, 6, 2},
> {2, 7,
> 4, 10, 9, 2}, {3, 7, 4, 10, 6, 3}, {
> 1, 2, 7, 6, 3, 10, 1}, {1, 2, 7, 6, 13,
> 10, 1}, {1, 2, 10, 6, 3, 7, 1}, {1, 7, 4,
> 10, 6, 13, 1}, {1, 7, 6, 3, 2, 10, 1}, {1, 10,
> 6, 3, 2, 7, 1}, {2, 7, 4, 10, 6, 3, 2}, {
> 2, 7, 6, 3, 10, 9, 2}, {2, 7, 6, 13, 10,
> 9, 2}, {2, 10, 6, 3, 7, 4, 2}, {2, 10, 6,
> 3, 7, 9, 2}, {1, 2, 7, 4, 10, 6, 13, 1}, {1,
> 7, 4, 2, 10, 6, 13, 1}, {1, 7, 9, 2, 10,
> 6, 13, 1}, {1, 10, 9, 2, 7, 6, 13, 1}}
>
>
> In general, the problem is that algorithms related to this graph feature
> seem to be very time consuming.
>
> The problem is: Given a graph via the adjacency matrix how can I find
> All circuits perhaps using the Mathematica command HamiltonianCycle.
>
> It would be great if anyone would have an idea how to solve it or at
> least a hint where to find a Mathematica formulated solution.
>
> Thanks in advance and
> Best regards
> Frank
>
>
>
>
>
Dear Frank,
I think you need to specify your problem better, but try this.
<<DiscreteMath`Combinatorica`
matrix={{0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,
0},{0,1,0,0,0,0,1,0,0,1,0,0,0,0,0,0},{0,1,0,0,0,0,1,0,0,1,1,0,0,0,0,
0},{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,
0},{1,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0},{0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0},{1,0,0,0,0,1,0,0,1,0,0,0,0,0,0,
0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,
0},{1,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0},{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0},{0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0}}
gr = FromAdjacencyMatrix[matrix]
ShowGraph[gr,VertexNumber\[Rule]True]
From this you can see that there is no Hamiltonian cycle on the
complete graph, confirmed by Ma.
HamiltonianCycle[gr]
Perhaps you are interested in finding a subgraph in which a Hamiltonian
cycle can be found. However the complete circuits you gave don't seem to
correspond to the paths in the graph. For example you show {2,10,6,2},
but there is no path between 10 and 6 or 6 and 2. Is there a problem
with your adjacency matrix? In any case the help for the
DiscreteMath`Combinatorica` package may be helpful.
LP
- References:
- Hamiltonian circuits
- From: Frank Brand <frank.brand@t-online.de>
- Hamiltonian circuits