MathGroup Archive 2006

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

Search the Archive

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


  • Prev by Date: Re: which polynomial interpolant is good for CDF representation
  • Next by Date: Network Protocol
  • Previous by thread: Hamiltonian circuits
  • Next by thread: Accuracy of Norm[{0``1}] is infinity?