In this degree titled "The chinese postman problem," two different variants of the Chinese postman problem are presented. The first part deals with an algorithm for solving the problem on an undirected graph, while the second part addresses an algorithm for solving the problem on a directed graph. In both cases, we are concerned with the problem of which edges to add to the graph to ensure the existence of an Eulerian cycle, where the cost of the added edges must be minimized. For undirected graphs, an algorithm is presented that pairs vertices of odd degree via shortest paths, while for directed graphs, the Hungarian method is discussed, which solves the minimum cost perfect matching problem. An alternative approach using the transshipment problem is also presented.
|
