WOLFRAM

Services & Resources / Wolfram Forums / MathGroup Archive

MathGroup Archive 2006

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

Search the Archive

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
  • Prev by Date: Re: A mistake by Mathematica?
  • Next by Date: List Question
  • Previous by thread: Re: Hamiltonian circuits
  • Next by thread: Re: Hamiltonian circuits