Optimal Graph Traversals
DOI link for Optimal Graph Traversals
Optimal Graph Traversals book
This chapter deals Eulerian-type problems, which require that each edge be traversed at least once. It is concerned with Hamiltonian-type problems, which involve traversals that must visit each vertex at least once. The use of the term Eulerian is identical for digraphs, except that all trails are directed. The characterizations of graphs that have Eulerian tours or open Eulerian trails apply to digraphs as well. Tarry's maze-searching algorithm follows a depth-first search strategy. The algorithm produces an Eulerian tour of the graph obtained by duplicating each edge of the input graph. The Chinese mathematician Meigu Guan introduced the problem of finding a shortest closed walk to traverse every edge of a graph at least once. The objective of the Chinese Postman Problem is to find an optimal postman tour in a given weighted graph, where the edge-weights represent some measurable quantity that depends on the application.