MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Odd graphic, looks different in different Adobe apps
  • Next by Date: Re: How to get a positive solution from Solve Command
  • Previous by thread: Hamiltonian circuits
  • Next by thread: Re: Hamiltonian circuits