FindPostmanTour

FindPostmanTour[g]

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 allclose all

Basic Examples  (2)

Find a Chinese postman tour:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

Highlight the tour:

In[3]:=
Click for copyable input
Out[3]=

Find several Chinese postman tours:

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

Scope  (8)

Applications  (3)

Properties & Relations  (2)

Neat Examples  (1)

See Also

FindEulerianCycle  FindHamiltonianCycle  FindShortestTour

Introduced in 2012
(9.0)
| Updated in 2015
(10.3)