3
$\begingroup$

The question is to show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem (ETSP) on $n$ points.

My attempt was using induction. So I start by:

  • If $n=3$, then we have a triangle and there is only one tour.
  • Assume that there are $(n-1)!/2$ distinct tours for a ETSP on $n$ points. Prove that there are $n!/2$ distinct tours for a ETSP on $n+1$ points?

    • Here I proceed like this:

      • for each tour $t$ from the $(n-1)!/2$ distinct tours do: add one point $n+1$.
      • for each edge $e=\{v_i, v_j\}$ in $t$ do: remove $e$ and create two edges $e_1=\{n+1,v_i\}$ and $e_2=\{n+1, v_j\}$. We have a new tour and in total we can create $n$ distinct tours.

        Since there are $(n-1)!/2$ distinct tours, we will have $n(n-1)!/2=n!/2$ distinct tours.

This gives the desired result but somehow long and complicated.

$\endgroup$
6
$\begingroup$

We may reason in a combinatorial way.

There are $n!$ permutations of $n$ nodes, but that overcounts the number of tours in two different ways. Since tours are closed, we may start indifferently on any of the $n$ nodes, and we may choose the direction in $2$ ways. Therefore, each tour was counted a total of $2n$ times.

This yields the desired result.

$\endgroup$
  • $\begingroup$ That is if n> 2. $\endgroup$ – gnasher729 Jan 17 '17 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.