Line 1: | Line 1: | ||
− | More Traversals of a Graph or Digraph<br>• Tour – visit each vertex in a graph exactly once and finish at the vertex started from.<br>• Eulerian tour – find a path/tour through the graph such that every edge is visited<br>exactly once. (Easy – check nodal degree; if all are even, it is possible.)<br>• Hamiltonian tour – find a path through the graph such that every vertex is visited<br>exactly once. (NP complete)<br>• See Figure 5 for different tours. | + | More Traversals of a Graph or Digraph<br>• Tour – visit each vertex in a graph exactly once and finish at the vertex started from.<br>• Eulerian tour – find a path/tour through the graph such that every edge is visited<br>exactly once. (Easy – check nodal degree; if all are even, it is possible.)<br>• Hamiltonian tour – find a path through the graph such that every vertex is visited<br>exactly once. (NP complete)<br>• See Figure 5 for different tours. |
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | [[Image:maoyi.jpg]] |
Revision as of 14:22, 16 April 2012
More Traversals of a Graph or Digraph
• Tour – visit each vertex in a graph exactly once and finish at the vertex started from.
• Eulerian tour – find a path/tour through the graph such that every edge is visited
exactly once. (Easy – check nodal degree; if all are even, it is possible.)
• Hamiltonian tour – find a path through the graph such that every vertex is visited
exactly once. (NP complete)
• See Figure 5 for different tours.