Re: Hamiltonian circuits
- To: mathgroup at smc.vnet.net
- Subject: [mg67917] Re: Hamiltonian circuits
- From: "Zhu Guohun" <ccghzhu at hrt.dis.titech.ac.jp>
- Date: Fri, 14 Jul 2006 02:11:07 -0400 (EDT)
- References: <e8lfpl$r18$1@smc.vnet.net><e8nt8i$k81$1@smc.vnet.net> <e8vtsb$st6$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Dear Frank Brand,
Your problem is obtain all of circuit from a simple directed graph
which include the symmetry edges.
I think in generally speaking, this problem is NP-hard. since
finding a Hamiltonian cycle in a graph is NP-hard.
recently I study the hamitlonian problem of directed graph without
symmetry edges, I think maybe find some speical cases that could solve
in polynomial time. but I could not prove it. For directed graph, the
number of reference is less than undirected graph.
-------------------
Zhu
Frank Brand wrote:
> 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