| 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.
