2
$\begingroup$

I was wondering if this is a solution to the TSP problem. For a set of $n$ points on the plane, the number of 'roads' in the plane such that there is a road between every point is $n\Bbb C 2$ = $n^2-n \over 2$

The total number of possible paths which connect all the points together is $n!$.

The Algorithm is as such:

*Assign weights(the length of the roads) to each road.

*Calculate the minimum spanning Tree for the graph (Algorithms exist to calculate in linear time.)

*Between the two end(free) vertices of the MST take the road.

*The cycle formed thus is the solution.

$\endgroup$
  • 4
    $\begingroup$ No. Simple way to prove it - run this solution and brute-force in the random small graphs $\endgroup$ – kotomord Nov 23 '16 at 12:52
  • $\begingroup$ Why would it be wrong. It seems to me, that it should be right. By definition, the MST is the shortest route connecting all points. Once we've found that, just connect the extremeties of the MST. $\endgroup$ – Tobi Alafin Nov 23 '16 at 14:05
  • 1
    $\begingroup$ To answer your question "why would it be wrong?" you should look carefully at some small counterexamples - as @kotomord suggests. What if the minimal spanning tree turns out to be a star? $\endgroup$ – Ethan Bolker Nov 23 '16 at 14:08
  • 1
    $\begingroup$ Can I be linked to them please? $\endgroup$ – Tobi Alafin Nov 23 '16 at 14:10
  • $\begingroup$ Here's a Stack Overflow post that discusses how minimum spanning trees can be used to find lower bounds for TSP: stackoverflow.com/questions/22985590/… $\endgroup$ – Math1000 Nov 23 '16 at 14:14
2
$\begingroup$

The weights of the edges need not be their lengths. In the TSP they are just costs - perhaps the salesman needs to take air fare into account.

Counterexample: suppose the cities are at the vertices of an equilateral triangle together with one city at the center. Then suppose the cost of traveling from the center to each of the three vertices is $0$ (or some small number if you like) while the cost of traveling along an edge is $1$. Then the MST is the graph consisting of the three spokes from the center.

The cheapest way for the salesman to visit all the cities is to go back and forth to the center. If she must travel in a cycle, use two edges of the triangle and two spokes. Neither of these is built from the spanning tree using your algorithm.

$\endgroup$
  • 1
    $\begingroup$ And even if you take edge lengths as the costs, the MST is still the same star, so the counterexample remains. $\endgroup$ – Rahul Nov 23 '16 at 15:33
0
$\begingroup$

It is true that the total weight of a minimum spanning tree gives us a lower bound on the minimum weight of a Hamiltonian tour in a graph. However, it also easy to find graphs for which a minimum spanning tree need not be a Hamiltonian tour. Consider e.g. any $n$-ary wheel graph for which the weight of each spoke is $1$ and every other edge has weigh $2$. The minimum spanning tree will have total weight $n-1$, whereas a minimum weight Hamiltonian tour must have total weight greater than $n-1$, as it will need to use at least one edge that is not a spoke.

The subgraph mentioned in the question, that is, a spanning tree together with an additional vertex connected to the tree by two edges, is what is known as a 1-tree. A classic paper by Held and Karp from 1970 shows a connection between 1-trees and Hamiltonian tours and shows how this leads to a branch-and-bound algorithm for searching for Hamiltonian tours below a given bound.

Moreover, there is a well-known approximate algorithm for solving the so-called metric Travelling Salesman Problem using minimum spanning trees. The metric TSP is one in which one only considers weight functions that satisfy the triangle inequality. See e.g. https://people.orie.cornell.edu/dpw/orie6300/Recitations/Rec12.pdf for more.

$\endgroup$
0
$\begingroup$

I think that if one nearest path for any one point is calculated. İt can be calculated in polynomial time.

  1. Line is generated with these shortest lines.
  2. Then all line's vertices combine with their nearest other line vertices.
  3. İf one point have $2$ or more nearest another point. (İt can be maximum $6$ because $\frac{2\pi}{6} = 60^{\circ}$. Therefore more than $6$ equal nearest another point generates in plane. Smaller than $60^{\circ}$ triangle generates for other two points a nearest line between them therefore one point have maximum $6$ equal nearest point.)

İn the end. We assume that all nearest points are one group. Then calculated nearest two points for these group. One nearest for generating line for exiting from this group another for generating line for intaking from this group. These steps calculates in polynomial time for TSP solution.

$\endgroup$
  • $\begingroup$ Welcome to math.se! Please read how to format mathematics here. Also you can find other formatting options, e. g., you can see labeled list. And don't forget about spaces after punctuation marks. I've edited your post, but that should not be done later. Good luck at math.se! $\endgroup$ – Smylic Apr 5 '17 at 22:20

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.