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