Chapter 4: The Chinese Postman Problem on Directed, Mixed, and Windy Graphs
Ángel Corberán, Isaac Plana, José María Sanchis · Society for Industrial and Applied Mathematics eBooks · 2015
4.1 ▪ Introduction Let G = (V,E,A) be a mixed graph, consisting of a set of vertices V, a set of (undirected) edges E, and a set of (directed) arcs A. For simplicity, the term link will be used to refer to both edges and arcs indistinctly. Note that if E = Ø, G is a directed graph (all the links are arcs that must be traversed in a specified direction), while if A= Ø, it is an undirected graph (all the links are edges that can be traversed in both directions at the same cost). Usually, the links in undirected, directed, and mixed graphs have a nonnegative cost associated with them. If G is an undirected graph and there are two costs associated with each edge, representing the cost of traversing it in each possible direction, G is called a windy graph. Note that, since any arc (i,j) with cost ci j can be modeled as an edge joining i and j with the same cost from i to j and infinite cost in the opposite direction, a mixed graph can be considered as a special case of a windy graph.