Editing Chinese postman problem (section)

==Directed solution==
On a directed graph, the same general ideas apply, but different techniques must be used. If the directed graph is Eulerian, one need only find  an Euler cycle. If it is not, one must find ''T''-joins, which in this case entails finding paths from vertices with an in-[[Degree (graph theory)|degree]] greater than their out-[[Degree (graph theory)|degree]] to those with an out-[[Degree (graph theory)|degree]] greater than their in-[[Degree (graph theory)|degree]] such that they would make in-degree of every vertex equal to its out-degree. This can be solved as an instance of the [[minimum-cost flow problem]] in which there is one unit of supply for every unit of excess in-degree, and one unit of demand for every unit of excess out-degree. As such it is solvable in O(|''V''|<sup>2</sup>|''E''|) time. A solution exists if and only if the given graph is [[strongly connected]].<ref name = "EdmondsJohnson" /><ref>{{citation |last1 = Eiselt | first1 = H. A. | last2 = Gendreau | first2 = Michel | last3 = Laporte | first3 = Gilbert | title = Arc Routing Problems, Part 1: The Chinese Postman Problem | journal = [[Operations Research (journal)|Operations Research]] | year = 1995 | volume = 43 | issue = 2 | pages = 231–242 | doi=10.1287/opre.43.2.231| doi-access = free | hdl = 11059/14013 | hdl-access = free }}</ref>