WOLFRAM

Wolfram Language & System Documentation Center
Wolfram Language Home Page »

FindPostmanTour
✖
FindPostmanTour

✖

finds a Chinese postman tour in the graph g of minimal length.

✖

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)Summary of the most common use cases

Find a Chinese postman tour:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-cs2avj
In[2]:=2
✖
https://wolfram.com/xid/0bh05gfvekxzyr-d3j6vr
Out[2]=2

Highlight the tour:

In[3]:=3
✖
https://wolfram.com/xid/0bh05gfvekxzyr-x08v5x
Out[3]=3

Find several Chinese postman tours:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-tstla2
In[2]:=2
✖
https://wolfram.com/xid/0bh05gfvekxzyr-h12suj
Out[2]=2

Scope  (8)Survey of the scope of standard use cases

FindPostmanTour works with undirected graphs:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-6xfgzl
Out[1]=1

Directed graphs:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-gx301e
Out[1]=1

Weighted graphs:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-ighgre
Out[1]=1

Multigraphs:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-i2s368
Out[1]=1

Find several Chinese postman tours:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-7yf5pw
Out[1]=1

Use rules to specify the graph:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-bndh30
Out[1]=1

FindPostmanTour returns an empty result for a graph with no Chinese postman tours:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-mflle1
Out[1]=1

FindPostmanTour works with large graphs:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-9r6myk
In[2]:=2
✖
https://wolfram.com/xid/0bh05gfvekxzyr-hfop3e
Out[2]=2

Applications  (3)Sample problems that can be solved with this function

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

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-cn85r0
In[2]:=2
✖
https://wolfram.com/xid/0bh05gfvekxzyr-2qer8o
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0bh05gfvekxzyr-8oel4b
Out[3]=3

The total distance:

In[4]:=4
✖
https://wolfram.com/xid/0bh05gfvekxzyr-kmfdmo
Out[4]=4

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):

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-uhymq

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

In[2]:=2
✖
https://wolfram.com/xid/0bh05gfvekxzyr-2fhrgq
Out[2]=2

Show the route:

In[3]:=3
✖
https://wolfram.com/xid/0bh05gfvekxzyr-nnx2ex
Out[3]=3

The total delivery time:

In[4]:=4
✖
https://wolfram.com/xid/0bh05gfvekxzyr-xpjz51
Out[4]=4
In[5]:=5
✖
https://wolfram.com/xid/0bh05gfvekxzyr-e2nwef
Out[5]=5
In[6]:=6
✖
https://wolfram.com/xid/0bh05gfvekxzyr-uoo2fy
Out[6]=6

Testing combinations of actions in a finite-state machine:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-tstyre

Generate a line graph:

In[2]:=2
✖
https://wolfram.com/xid/0bh05gfvekxzyr-97m3h
Out[2]=2

A length-2 switch cover:

In[3]:=3
✖
https://wolfram.com/xid/0bh05gfvekxzyr-gd7s69
Out[3]=3

Properties & Relations  (2)Properties of the function, and connections to other functions

An Eulerian graph has a Chinese postman tour:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-3gsxfv
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0bh05gfvekxzyr-w1eufl
Out[2]=2
In[3]:=3
✖
https://wolfram.com/xid/0bh05gfvekxzyr-fxgz75
Out[3]=3

It is the same as its Eulerian cycle:

In[4]:=4
✖
https://wolfram.com/xid/0bh05gfvekxzyr-y1foos
Out[4]=4

A connected graph has a Chinese postman tour:

In[1]:=1
✖
https://wolfram.com/xid/0bh05gfvekxzyr-5b71og
Out[1]=1
In[2]:=2
✖
https://wolfram.com/xid/0bh05gfvekxzyr-h9dgvf
Out[2]=2

Neat Examples  (1)Surprising or curious use cases

Find a Chinese postman tour:

In[6]:=6
✖
https://wolfram.com/xid/0bh05gfvekxzyr-u0eavy
In[7]:=7
✖
https://wolfram.com/xid/0bh05gfvekxzyr-4pqe81
Out[7]//Shallow=7

Dynamically highlight cycles:

In[8]:=8
✖
https://wolfram.com/xid/0bh05gfvekxzyr-icixe
In[11]:=11
✖
https://wolfram.com/xid/0bh05gfvekxzyr-dnw6p
Out[11]=11
Wolfram Research (2012), FindPostmanTour, Wolfram Language function, https://reference.wolfram.com/language/ref/FindPostmanTour.html (updated 2015).
✖
Wolfram Research (2012), FindPostmanTour, Wolfram Language function, https://reference.wolfram.com/language/ref/FindPostmanTour.html (updated 2015).

Text

Wolfram Research (2012), FindPostmanTour, Wolfram Language function, https://reference.wolfram.com/language/ref/FindPostmanTour.html (updated 2015).

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

✖
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

✖
Wolfram Language. (2012). FindPostmanTour. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindPostmanTour.html

BibTeX

@misc{reference.wolfram_2025_findpostmantour, author="Wolfram Research", title="{FindPostmanTour}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindPostmanTour.html}", note=[Accessed: 30-March-2025 ]}

✖
@misc{reference.wolfram_2025_findpostmantour, author="Wolfram Research", title="{FindPostmanTour}", year="2015", howpublished="\url{https://reference.wolfram.com/language/ref/FindPostmanTour.html}", note=[Accessed: 30-March-2025 ]}

BibLaTeX

@online{reference.wolfram_2025_findpostmantour, organization={Wolfram Research}, title={FindPostmanTour}, year={2015}, url={https://reference.wolfram.com/language/ref/FindPostmanTour.html}, note=[Accessed: 30-March-2025 ]}

✖
@online{reference.wolfram_2025_findpostmantour, organization={Wolfram Research}, title={FindPostmanTour}, year={2015}, url={https://reference.wolfram.com/language/ref/FindPostmanTour.html}, note=[Accessed: 30-March-2025 ]}