TSP and Minimum Weighted Route

[Nikhar]

Hi,
Suppose there's a weighted undirected graph G(V,E) where each weight is the distance between two vertices. I have to visit all the vertices of the graph such that the total distance travelled is minimum.
Is this an instance of Traveling Salesman Problem?

Following is the amount of work that I've done on the problem so far.

Since the TSP states that each vertex has to be visited exactly once, for the problem stated to be an instance of TSP, G(V,E) must be a complete graph. Otherwise, it may not be possible to go to all the vertices without visiting some vertices more than once.
For example,

D-B-C
  |
  A

if we begin from A, we will have to go to B twice so as to reach all vertices.

The next thing that I figured out is that if G(V,E) satisfies triangular inequality, then the minimum weighted route will not visit each vertex more than once. Following is the proof that I came up with:-

Suppose, a portion of a complete graph is:-

D-B-C
  |
  A

Suppose, in the total minimum distance route , there is some edge A-B and and some edge B-D where vertex B is visited twice and is not the starting vertex.
So, there exists a path D-> ... ->u -> v -> ..... ->B where u and v are some vertices of graph.
So, one of the paths is A-> B -> D-> ...u...v...-> B. Let this be 'Path 1'.

Now, since the triangular inequality says:-
weight(AD) < weight (AB) + weight (BD)..

So, if we replace the subpath A -> B -> D in 'Path 1' with A -> D, the path becomes:- A -> D -> ...u...v...->B. Let this path be 'Path 2'.

From triangular inequality, we can say that total weight of Path 2 is less than Path 1. Also, Path 2 touches all those vertices touched by Path 1.

So, the minimum distance route will have Path 2 and not Path 1. Hence, no vertex will be visited twice.

As far as I see it, the proof seems to be correct. But since, I have never been good at proofs, I'd love it if you guys could assure me that it's correct. Or point out the fault in it.

Considering that whatever I have written until now is correct, can I say the follwing?

For TSP to be similar to the minimum weight route problem stated above, the conditions:-

1.) graph must be complete

2.) graph must satisfy triangular inequality

are necessary and sufficient?

[Momerath]

Triangular inequality doesn't have to hold for a graph, nor for the TSP problem. Consider a situation where the route from AD is not direct, but wanders around the countryside.

[Taywin]

Your problem is not about TSP. You could read this post from other site about how to solve your problem.

[Nikhar]

Hi,
@Momerath and @Taywin... thanks for your replies. :)
I guess I wasn't clear enough about the question. I am not saying that triangular inequality should hold in TSP... that is a specialization of TSP - the metric TSP. All I'm saying (or rather asking) is that if my graph G(V,E) according to which the truck has to deliver goods is complete and it satisfies T.I. , then the problem of 'finding the route the truck must take so as to travel minimum distance' and TSP is one and the same.

[Taywin]

Yes, you are correct. But that doesn't mean it will help you solve your problem. As you said, if there is a path from D->...->u->v->...->B and then you found that it is shorter to go from A->D rather than A->B->D, it still doesn't help you because you will eliminate the path to visit vertex B. As a result, it is not a minimal path for you because you will have to recalculate to find a way to include B later on if the graph doesn't contain Hamiltonian path.

[Momerath]

I agree with Taywin. The problem is TSP, having the nodes satisfy TI just makes the graphs a subset of all graphs, but doesn't change the problem.