Travelling salesman problem

[Mitch Harris]

If I understand your graph correctly (it looks like it should be P_n x
P_n) then the number of shortest paths is the number of paths that can
only go down (choosing left or right when possible). This is
equivalent to strings of L and R of length 2n having exactly n L's and
n R's in any order, which is the same as the number of subsets of size
n from a set of size 2n or:

  {2n \choose n} = (2n)!/(n!^2)

(given that your graph's are:
  F
 / \
x   x
 \ /
 S

and:

  F
 / \
 x x
/ \ / \
x x x
\ / \ /
 x  x
  \ /
  S

 (these are called 'grid graphs' in the English combinatorics literature)

On Dec 6, 2007 12:03 PM, Artur <grafix at csl.pl> wrote:
> And how many is different the shortest roads ?
>
> Artur pisze:
>
> > I was think about travelling salseman problem (Problem NP
> > completeness). If problem is poor defined let on the start in
> > symmetric trangular graphs with constant distance between neighborough
> > vertices
> > these graphs have n2 vertices. Sealsman have to reached each vertice
> > (but not necessary go through each edge and some edge two times
> > available)
> >
> > For 4  vertices  (S=Start F=Finsih)
> >
> >  F
> > x     x
> >  S
> >
> > For 9 vertices
> >      F
> >   x    x
> > x     x      x
> > x      x
> >     S
> > etc
> >
> > __________ NOD32 Informacje 2701 (20071204) __________
> >
> > Wiadomosc zostala sprawdzona przez System Antywirusowy NOD32
> > http://www.nod32.com lub http://www.nod32.pl
> >
> >
>



-- 
Mitch Harris