# optimal way in graph? - Graphics

This is a discussion on optimal way in graph? - Graphics ; want to find a way from a start vertice to visit the other vertices in a graph. constraints: 1. a way with min. edges 2. need not to visit all the vertices of this graph, but the unvisit vertices should ...

1. ## optimal way in graph?

want to find a way from a start vertice to visit the other vertices in
a graph.
constraints:
1. a way with min. edges
2. need not to visit all the vertices of this graph, but the unvisit
vertices should have max. 2 edges to one of the visited vertices on
this way

2. ## Re: optimal way in graph?

CC.TUDresden@gmail.com schrieb:
> want to find a way from a start vertice to visit the other vertices in
> a graph.
> constraints:
> 1. a way with min. edges

This ist the travelling salesman problem which is NP complete. Look at
http://www.ameisenalgorithmus.de/
> 2. need not to visit all the vertices of this graph, but the unvisit
> vertices should have max. 2 edges to one of the visited vertices on
> this way
>

3. ## Re: optimal way in graph?

Steffen Koehler 写道：

> CC.TUDresden@gmail.com schrieb:
> > want to find a way from a start vertice to visit the other vertices in
> > a graph.
> > constraints:
> > 1. a way with min. edges

> This ist the travelling salesman problem which is NP complete. Look at
> http://www.ameisenalgorithmus.de/
> > 2. need not to visit all the vertices of this graph, but the unvisit
> > vertices should have max. 2 edges to one of the visited vertices on
> > this way
> >

but this is not a salesman problem, while the vertices can be visited
many times, and the edges have the same length, the vertices can only
visit its neighbor vertices

4. ## Re: optimal way in graph?

<CC.TUDresden@gmail.com> wrote in message

> but this is not a salesman problem, while the vertices can be visited
> many times, and the edges have the same length, the vertices can only
> visit its neighbor vertices

Is it a special tree you are trying to build?

5. ## Re: optimal way in graph?

Uffe Kousgaard 写道：

> <CC.TUDresden@gmail.com> wrote in message