Travelling salesman problem

[Mitch Harris]

>
>   {2n \choose n} = (2n)!/(n!^2)
>
> (given that your graph's are:

(argh...pardon the poor formatting...tried to do it in varwidth font)

  F
 / \
x   x
 \ /
  S

and:

    F
   / \
  x   x
 / \ / \
x   x   x
 \ / \ /
  x   x
   \ /
    S
>
>  (these are called 'grid graphs' in the English combinatorics literature)



aj> From grafix at csl.pl  Thu Dec  6 17:53:32 2007
aj> Return-Path: <grafix at csl.pl>
aj> Date: Thu, 06 Dec 2007 17:53:48 +0100
aj> From: Artur <grafix at csl.pl>
aj> Reply-To: grafix at csl.pl
aj> To: Richard Mathar <mathar at strw.leidenuniv.nl>
aj> Subject: Re: Re^2: A109094 maximum salesman path in K_n
aj> 
aj> I was think about travelling salseman problem (Problem NP completeness). 
aj> If problem is poor defined let on the start in symmetric trangular 
aj> graphs with constant distance between neighborough vertices
aj> these graphs have n^2 vertices. Sealsman have to reached each vertice 
aj> (but not necessary go through each edge and some edge two times available)
aj> 
aj> For 4  vertices  (S=Start F=Finsih)
aj> 
aj>    F
aj> x     x
aj>    S
aj> 
aj> For 9 vertices
aj>        F
aj>     x    x
aj> x     x      x
aj>   x      x
aj>       S
aj> etc

If one tilts the graph by 45 degrees, one gets a simple square grid

x  x  x  x  F
x  x  x  x  x
x  x  x  x  x
S  x  x  x  x

The output depends on which streets (edges) are inserted. If the 
edges are all North-South or East-West,  never diagonal, the following
meandering path would be the solution if n is odd, with one edge needed for
each of the vertices :

|->|   |->-|   F
^  |   ^   |   ^
|  |   |   |   |    <= n odd
S  |-->|   |->-|

The path length is n^2-1. There are other solutions of this type with
a more irregular maze type, but of the same length. If n is even, one ends up at
an opposite edge of F and needs at most n-1 additional edges to make
it back to F.

|--|   |---F
|  |   |   |
|  |   |   |   <= n even
S  |---|   |

But a better solution for n even is to move to the "column" of F one step
earlier and then to use a wrinkled path in the last two columns upwards:

|--|   |<>-F
|  |       |
|  |   |->-
|  |   |   
|  |   |-<-|   <= n even
|  |       ^   <= n even
S  |--------

This seems to need n^2 edges, the n^2-1 from above, plus the last one used
again in opposite direction to finish in F.

Richard