| 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.png]] |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | [[Image:maoyi. | + | |
Revision as of 14:23, 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. 
