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