O problema chinês do carteiro: um convite à Teoria dos Grafos

Abstract

The present work addresses the Chinese Postman Problem (CCP), which is used to solve path problems by providing the least cost walk (path) in a graph. This aims to invite the reader to know the Theory of Graphs through a study of the PCC. At the beginning of the work, the fundamentals of the theory are approached, such as: concepts; Definitions; notions among others, which is fundamental for any study involving the theory. In the PCC there are some cases of Graphs, the most common cases being: Non-Oriented Graph; Oriented Graph and Mixed Graph. In each case, the problem basically boils down to transforming the graph into Eulerian and finding a minimum-cost walk through each edge of this graph at least once through algorithms. A formulation of Linear Programming for the PCC will also be discussed, in order to show another way to obtain the resolution of problems of this nature.