Re: [Tcllib-devel] ping gsoc graph work ...

[Lars H. <Lar...@re...>]

Michał Antoniewski skrev:
> Hello.
> 
> I updated some tests for Max-Cut ( testing subprocedures seperately ).
> 
> And now TSP.
> 
> After some rethinking I came up with such solution to handle those
> uncomplete graphs:
> - first step filling graph with edges to have a complete graph. At the same
> time saving set of original Edges. Weights on new edges are set to Inf. [ In
> practise algorithm is avoiding them anyway, so maybe it's even not needed to
> take that step ].

As Andreas has already remarked, this will typically violate the 
triangle inequality, thus rendering the TSP instance non-metric. But 
the proof that converting a tour to a cycle by taking shortcuts doesn't 
increase the combined weight requires the problem to be metric, so 
you'd be in trouble here.

[snip]
> - what I described assumes that we accept doubled occurances of nodes in
> solution. Going back to definition of the problem - it says that there
> shouldn't be such situations ( TSP problem is finding shortest Hamilton
> Cycle, with only one occurance of each vertex ). So, now it's time to
> decide, what to do: give that solution I describe above, or in such case
> return error that it's not Hamilton's graph ( don't know if I wrote it well,
> but I mean graph without proper Hamilton cycle ).

A graph with a Hamilton cycle is said to be /Hamiltonian/, so I suppose 
the term you were looking for here is "non-Hamiltonian".

"Hamilton's graph" _might_ be taken as a reference to the dodekahedron, 
because of the icosian game: http://en.wikipedia.org/wiki/Icosian_game


Lars Hellström