FindPostmanTour
finds a Chinese postman tour in the graph g of minimal length.
FindPostmanTour[g,k]
finds at most k Chinese postman tours.
FindPostmanTour[{vw,…},…]
uses rules vw to specify the graph g.
Details
- A Chinese postman tour is a tour that traverses each edge at least once.
- FindPostmanTour returns a list of edges consisting of Chinese postman tours.
- FindPostmanTour returns the list {} if no Chinese postman tours exist.
- FindPostmanTour[g] is equivalent to FindPostmanTour[g,1].
- FindPostmanTour works with undirected graphs, directed graphs, weighted graphs, and multigraphs.
Examples
open all close allBasic Examples (2)
g = [image];FindPostmanTour[g]//FirstTable[HighlightGraph[g, %[[1 ;; i]]], {i, 0, Length[%]}]Find several Chinese postman tours:
g = GraphData["ParachuteGraph"];FindPostmanTour[g, 2]Scope (8)
FindPostmanTour works with undirected graphs:
FindPostmanTour[[image]]FindPostmanTour [[image]]FindPostmanTour[[image]]FindPostmanTour[[image]]Find several Chinese postman tours:
FindPostmanTour[[image], 3]Use rules to specify the graph:
FindPostmanTour[{1 -> 4, 4 -> 3, 4 -> 2, 2 -> 3, 3 -> 1}]FindPostmanTour returns an empty result for a graph with no Chinese postman tours:
FindPostmanTour[[image]]FindPostmanTour works with large graphs:
g = GridGraph[{10, 10, 10}];FindPostmanTour[g]//Short//TimingApplications (3)
Find a shortest route that a newspaper carrier can use to distribute newspapers in a neighborhood:
g = [image];route = First[FindPostmanTour[g]]Length[route]Total[AnnotationValue[{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 = [image];A route that goes through all the streets and minimizes the total deadheading time:
route = First[FindPostmanTour[g]]Annotate[g, Epilog -> {Arrowheads[Join[{0}, ConstantArray[.06, 11]]], Thickness[.01], Opacity[.5], Orange, Arrow[BSplineCurve[(AnnotationValue[{g, #}, VertexCoordinates]& /@ Append[route[[All, 1]], "A"]), SplineDegree -> 2]]}]deliverytime = Total[AnnotationValue[{g, #}, "DeliveryTime"]& /@ EdgeList[g]]deadheadtime = Total[AnnotationValue[{g, #}, EdgeWeight]& /@ route] - Total[AnnotationValue[{g, #}, EdgeWeight]& /@ EdgeList[g]]deadheadtime + deliverytimeTesting combinations of actions in a finite-state machine:
g = [image];VertexReplace[LineGraph[g], Thread[Range[EdgeCount[g]] -> EdgeList[g]], VertexLabels -> Placed["Name", Above]]Map[First, First[FindPostmanTour[%]], {2}]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[{12, 23, 31, 45, 56, 64, 34}]{ConnectedGraphQ[g], FindPostmanTour[g]}Neat Examples (1)
g = [image];Shallow[tour = First[FindPostmanTour[g]]]color[tours_] := {tours, tours[[All, 1]], Style[tours[[-1, 2]], Yellow]}Dynamic[HighlightGraph[g, color[tour[[1 ;; Clock[{1, Length[tour], 1}, 40]]]]]]Text
Wolfram Research (2012), FindPostmanTour, Wolfram Language function, https://reference.wolfram.com/language/ref/FindPostmanTour.html (updated 2015).
CMS
Wolfram Language. 2012. "FindPostmanTour." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindPostmanTour.html.
APA
Wolfram Language. (2012). FindPostmanTour. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindPostmanTour.html