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?
