Services & ResourcesWolfram ForumsMathGroup Archive

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

Hamiltonian circuits

• To: mathgroup at smc.vnet.net
• Subject: [mg67774] Hamiltonian circuits
• From: Frank Brand <frank.brand at t-online.de>
• Date: Fri, 7 Jul 2006 07:12:47 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

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

• Follow-Ups:
  • Re: Hamiltonian circuits
    • From: leigh pascoe <leigh@cephb.fr>