James Emil Avery wrote:
>
> Givet en orienteret graf oensker jeg at finde laengden af en minimal
> sti, som besoeger alle knuder.
>
> Om muligt, vil jeg gerne udnytte foelgende struktur paa grafen: Jeg
> starter med en n-regulaer graf med diameter to over n^2 knuder. For hver
> knude v findes en Hamilton-sti, som starter og slutter i v. Nu fjerner
> jeg k knuder og skal konstruere en sti af minimal laengde, som besoeger
> hver af de tilbagevaerende n^2-k knuder mindst een gang. Kan jeg sige
> noget fornuftigt vedroerende en oevre graense for laengden af en saadan
> minimal sti? Jeg paastar, at denne laengde er opadtil begraenset af 2n^2
> uanset k. Men hvilke vaerktoejer kan jeg bruge til at bevise det?
>
> Enhver hjaelp vil blive modtaget med kyshaand!
>
Hej James
Det er vist i denne boldgade:
http://en.wikipedia.org/wiki/Travelling_salesman_problem
hilsen
Glenn