MathGroup Archive 2006

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

Search the Archive

Re: Hamiltonian circuits

  • To: mathgroup at smc.vnet.net
  • Subject: [mg67805] Re: Hamiltonian circuits
  • From: "Zhu Guohun" <ccghzhu at hrt.dis.titech.ac.jp>
  • Date: Sat, 8 Jul 2006 04:56:19 -0400 (EDT)
  • References: <e8lfpl$r18$1@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

As you point out, the {1,7,1} is a circuit. but as many reference about
graph theory , a cycle include more than 3 verteices. what is your
cycle definition


  • Prev by Date: Speed challenge integer frequencies: and the winner is...
  • Next by Date: Re: Subvalues and Parameters in Differentiation and Usage Messages
  • Previous by thread: Re: Hamiltonian circuits
  • Next by thread: Hamiltonian circuits