({{, (RefLink[FindPostmanTour, paclet:ref/FindPostmanTour])[g] 
finds a Chinese postman tour in the graph g of minimal length.}, {, (RefLink[FindPostmanTour, paclet:ref/FindPostmanTour])[g,k]
finds at most k Chinese postman tours. }, {, (RefLink[FindPostmanTour, paclet:ref/FindPostmanTour])[{v->w,…},…]
uses rules v->w to specify the graph g.}})

OpenersNotesSection(Spacer1)Details

A Chinese postman tour is a tour that traverses each edge at least once.

(RefLink[FindPostmanTour, paclet:ref/FindPostmanTour]) returns a list of edges consisting of Chinese postman tours.

(RefLink[FindPostmanTour, paclet:ref/FindPostmanTour]) returns the list {} if no Chinese postman tours exist.

(RefLink[FindPostmanTour, paclet:ref/FindPostmanTour])[g] is equivalent to (RefLink[FindPostmanTour, paclet:ref/FindPostmanTour])[g,1].

(RefLink[FindPostmanTour, paclet:ref/FindPostmanTour]) works with undirected graphs, directed graphs, weighted graphs, and multigraphs.

OpenersPrimaryExamplesSection(Spacer1)Examples  (16)

OpenersExampleSection0(Spacer1)Basic Examples  (2)

Find a Chinese postman tour:

g=;

FindPostmanTour[g]//First

Highlight the tour:

Table[HighlightGraph[g,%[[1;;i]]],{i,0,Length[%]}]

Find several Chinese postman tours:

g=GraphData["ParachuteGraph"];

FindPostmanTour[g,2]

OpenersExampleSection1(Spacer1)Scope  (8)

(RefLink[FindPostmanTour, paclet:ref/FindPostmanTour]) works with undirected graphs:

FindPostmanTour[]

Directed graphs:

FindPostmanTour []

Weighted graphs:

FindPostmanTour[]

Multigraphs:

FindPostmanTour[]

Find several Chinese postman tours:

FindPostmanTour[,3]

Use rules to specify the graph:

FindPostmanTour[{1->4,4->3,4->2,2->3,3->1}]

(RefLink[FindPostmanTour, paclet:ref/FindPostmanTour]) returns an empty result for a graph with no Chinese postman tours:

FindPostmanTour[]

(RefLink[FindPostmanTour, paclet:ref/FindPostmanTour]) works with large graphs:

g=GridGraph[{10,10,10}];

FindPostmanTour[g]//Short//Timing

OpenersExampleSection3(Spacer1)Applications  (3)

Find a shortest route that a newspaper carrier can use to distribute newspapers in a neighborhood:

g=;

route=First[FindPostmanTour[g]]

Length[route]

The total distance:

Total[PropertyValue[{g,#},EdgeWeight]&/@route]

Find the most efficient way for a letter carrier to deliver letters, knowing the time it takes to deliver mail on a street and the time it takes to walk a street without delivering mail (deadheading time):

g=;

A route that goes through all the streets and minimizes the total deadheading time:

route=First[FindPostmanTour[g]]

Show the route:

SetProperty[g,Epilog->{Arrowheads[Join[{0},ConstantArray[.06,11]]],Thickness[.01],Opacity[.5],Orange,Arrow[BSplineCurve[(PropertyValue[{g,#},VertexCoordinates]&/@Append[route[[All,1]],"A"]),SplineDegree->2]]}]

The total delivery time:

deliverytime=Total[PropertyValue[{g,#},"DeliveryTime"]&/@EdgeList[g]]

deadheadtime=Total[PropertyValue[{g,#},EdgeWeight]&/@route]-Total[PropertyValue[{g,#},EdgeWeight]&/@EdgeList[g]]

deadheadtime+deliverytime

Testing combinations of actions in a finite-state machine:

g=;

Generate a line graph:

VertexReplace[LineGraph[g],Thread[Range[EdgeCount[g]]-> EdgeList[g]], VertexLabels->Placed["Name", Above]]

A length-2 switch cover:

Map[First,First[FindPostmanTour[%]],{2}]

OpenersExampleSection4(Spacer1)Properties & Relations  (2)

An Eulerian graph has a Chinese postman tour:

g=GraphData["OctahedralGraph"]

EulerianGraphQ[g]

FindPostmanTour[g]

It is the same as its Eulerian cycle:

FindEulerianCycle[g] == %

A connected graph has a Chinese postman tour:

g=Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1,4\[UndirectedEdge]5,5\[UndirectedEdge]6,6\[UndirectedEdge]4,3\[UndirectedEdge]4}]

{ConnectedGraphQ[g],FindPostmanTour[g]}

OpenersExampleSection5(Spacer1)Neat Examples  (1)

Find a Chinese postman tour:

g=;

Shallow[tour=First[FindPostmanTour[g]]]

Dynamically highlight cycles:

color[tours_]:={tours,tours[[All,1]],Style[tours[[-1,2]],Yellow]}

Dynamic[HighlightGraph[g,color[tour[[1;;Clock[{1,Length[tour],1},40]]]]]]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[FindEulerianCycle, paclet:ref/FindEulerianCycle])  ▪  (RefLink[FindHamiltonianCycle, paclet:ref/FindHamiltonianCycle])  ▪  (RefLink[FindShortestTour, paclet:ref/FindShortestTour])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Paths, Cycles, and Flows, paclet:guide/GraphPathsCyclesAndFlows])}, {▪(RefLinkPlain[Computation on Graphs, paclet:guide/ComputationOnGraphs])}})}})