Services & ResourcesWolfram ForumsMathGroup Archive

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

Hamiltonian circuits

• To: mathgroup at smc.vnet.net
• Subject: [mg67878] Hamiltonian circuits
• From: Frank Brand <frank.brand at t-online.de>
• Date: Tue, 11 Jul 2006 05:58:54 -0400 (EDT)
• References: <e8lfpl$r18$1@smc.vnet.net> <e8nt8i$k81$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Dear Zhu Guohun , Dear Leigh,

thanks for your postings. Indeed I made a mistake concerning my 
adjacency matrix.

The correct one is

AdjMatrix = {{0, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 
0, 1,
       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, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {1, 1, 1, 0, 1, 
0, 1,
       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 
0, 0,
       0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0}, {0, 1, 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, 1, 0, 0, 0, 0, 0, 0, 0, 1, 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, 
0, 0,
       0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1}, {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, 
0, 0,
       0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0}, {0, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 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, 1, 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, 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, 0, 0, 0, 0, 1, 1, 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, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 1,
       0, 0, 0, 1, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 1, 0, 0, 0,
     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}

So, in my special field of interest I also treat {1, 2, 1} as a circuit 
allthough in the literature the mathematical definition needs at least 
three vertices.

In the case of the above adjacency matrix there are the following list 
of all possible circuits on all subgraphs of the original graph.



AllCircuits=
{{1, 2, 1}, {5, 19, 5}, {13, 14, 13}, {1, 3, 2, 1}, {6, 13, 14, 6}, {6, 20,
   21, 6}, {1, 11, 18, 8, 1}, {2, 6, 19, 5, 2}, {8, 17, 19, 18,
    8}, {1, 11, 18, 9, 2, 1}, {2, 6, 19, 18, 9, 2}, {1, 2, 6, 19, 18, 8,
   1}, {1, 3, 15, 11, 18, 8, 1}, {1, 11, 18, 8, 9, 2, 1}, {2, 6, 13, 12, 
18, 9,
    2}, {2, 6, 16, 11, 18, 9, 2}, {2, 6, 19, 18, 8, 9, 2}, {2, 6, 20, 
12, 18,
      9, 2}, {5, 19, 18, 8, 17, 10, 5}, {8, 17, 10, 15, 11, 18, 8}, {
   1, 2, 6, 13, 12, 18, 8, 1}, {1, 2, 6, 16, 11, 18, 8,
    1}, {1, 2, 6, 20, 12, 18, 8, 1}, {1, 3, 2, 6, 19,
    18, 8, 1}, {1, 3, 15, 11, 18, 9, 2, 1}, {2, 6, 13,
   12, 18, 8, 9, 2}, {2, 6, 13, 16, 11, 18, 9, 2}, {2,
   6, 16, 11, 18, 8, 9, 2}, {2, 6, 20, 12, 18, 8, 9,
   2}, {2, 6, 20, 16, 11, 18, 9, 2}, {5, 16, 11, 18, 8,
    17, 10, 5}, {5, 16, 11, 18, 8, 17, 19, 5}, {6, 19, 18, 8, 17, 10, 
21, 6}, {
     1, 2, 6, 13, 16, 11, 18, 8, 1}, {1, 2, 6, 20, 16, 11, 18, 8, 1}, {1,
     3, 2, 6, 13, 12, 18, 8,
    1}, {1, 3,
   2, 6, 16, 11, 18, 8, 1}, {1, 3, 2, 6, 20, 12, 18, 8, 1}, {1, 3, 15, 11,
   18, 8, 9, 2, 1}, {1, 11, 18, 8, 17, 10, 5, 2, 1}, {1, 11, 18, 8, 17, 19,
      5, 2, 1}, {2, 6, 13, 12, 16, 11, 18, 9, 2}, {2,
    6, 13, 16, 11, 18, 8, 9, 2}, {2, 6, 19, 5, 16, 11, 18, 9, 2}, {2, 6,
   19, 18, 8, 17, 10, 5, 2}, {2, 6, 20, 12, 16, 11, 18, 9, 2}, {2, 6,
    20, 16, 11, 18, 8, 9, 2}, {6, 13, 12, 18, 8, 17, 10, 21, 6}, {6,
   16, 11, 18, 8, 17, 10, 21, 6}, {6, 20, 12, 18, 8, 17, 10, 21, 6}, {1, 2,
     6, 13, 12, 16, 11, 18, 8, 1}, {1, 2, 6, 19, 5, 16, 11, 18, 8,
    1}, {1, 2, 6, 20, 12, 16, 11, 18, 8, 1}, {1, 3, 2, 6, 13, 16, 11,
    18, 8, 1}, {1, 3, 2, 6, 20, 16, 11, 18, 8, 1}, {2, 6, 13, 12, 16, 11,
    18, 8, 9, 2}, {2, 6, 13, 12, 18, 8, 17, 10, 5, 2}, {2, 6, 13, 12, 18,
    8, 17, 19, 5, 2}, {2, 6, 16, 11, 18, 8, 17, 10, 5, 2}, {2, 6, 16, 11,
    18, 8, 17, 19, 5, 2}, {2, 6, 19, 5, 16, 11, 18, 8, 9, 2}, {2, 6, 20, 
12,
   16, 11, 18, 8, 9, 2}, {2, 6, 20, 12, 18, 8,
   17, 10, 5, 2}, {2, 6, 20, 12, 18, 8, 17, 19, 5, 2}, {6, 13, 16, 11, 
18, 8,
      17, 10, 21,
    6}, {6, 20, 16, 11, 18, 8, 17, 10, 21, 6}, {1, 3, 2, 6, 13, 12, 16, 
11, 18,
      8, 1}, {1, 3,
    2, 6, 19, 5, 16, 11, 18, 8, 1}, {1, 3, 2, 6, 20, 12, 16, 11, 18, 8, 
1}, {
     1, 3, 15, 11, 18, 8, 17, 10,
    5, 2, 1}, {1, 3, 15, 11, 18, 8, 17, 19, 5, 2, 1}, {2, 6, 13, 16, 11, 
18,
     8, 17, 10, 5, 2}, {2, 6, 13, 16, 11, 18, 8, 17, 19, 5, 2}, {2, 6, 
20, 16,
     11, 18, 8, 17,
    10, 5, 2}, {2, 6, 20, 16, 11, 18, 8, 17, 19, 5, 2}, {5, 16, 11, 18, 8,
     17, 10, 21, 6, 19, 5}, {6, 13, 12, 16, 11, 18, 8, 17, 10, 21, 6}, {6,
     20, 12, 16, 11, 18, 8,
    17, 10, 21, 6}, {1, 11, 18, 8, 17, 10, 21, 6, 19, 5, 2, 1}, {2, 6, 13,
     12, 16, 11, 18, 8, 17, 10, 5, 2}, {2, 6, 13, 12, 16, 11, 18, 8, 17,
     19, 5, 2}, {2, 6, 20, 12, 16, 11, 18, 8, 17, 10, 5, 2}, {2, 6, 20, 12,
      16, 11, 18, 8, 17, 19, 5, 2}, {1, 3,
   15, 11, 18, 8, 17, 10, 21, 6, 19, 5, 2, 1}}


I read very carefully the entire documentation of the combinatorica 
package but it seems that there is no procedure with a good time 
behaviour to detect all subgraphs containing Hamiltonian cycles?

Any help or hints are very welcome.

Greetings
Frank