WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

FindPostmanTour[g]

グラフ g の最短の中国人郵便配達順路を求める．

FindPostmanTour[g,k]

最高で k の中国人郵便配達順路を求める．

FindPostmanTour[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細
Details and Options Details and Options
例題  
例  
スコープ  
アプリケーション  
特性と関係  
おもしろい例題  
関連項目
関連するガイド
履歴
引用書式

FindPostmanTour

FindPostmanTour[g]

グラフ g の最短の中国人郵便配達順路を求める．

FindPostmanTour[g,k]

最高で k の中国人郵便配達順路を求める．

FindPostmanTour[{vw,…},…]

規則 vw を使ってグラフ g を指定する．

詳細

  • 中国人郵便配達順路とはすべての辺を少なくとも1回通る順路のことである．
  • FindPostmanTourは中国人郵便配達順路からなる辺のリストを返す．
  • FindPostmanTourは，中国人郵便配達順路が存在しない場合は{}を返す．
  • FindPostmanTour[g]はFindPostmanTour[g,1]と等価である．
  • FindPostmanTourは，無向グラフ，有向グラフ，重み付きグラフ，多重グラフに使うことができる．

例題

すべて開く すべて閉じる

例  (2)

中国人郵便配達順路を求める：

Wolfram Language code: g = [image];
Wolfram Language code: FindPostmanTour[g]//First

順路をハイライトする：

Wolfram Language code: Table[HighlightGraph[g, %[[1 ;; i]]], {i, 0, Length[%]}]

中国人郵便配達順路を数通り求める：

Wolfram Language code: g = GraphData["ParachuteGraph"];
Wolfram Language code: FindPostmanTour[g, 2]

スコープ  (8)

FindPostmanTourは無向グラフに使うことができる：

Wolfram Language code: FindPostmanTour[[image]]

有向グラフに使う：

Wolfram Language code: FindPostmanTour [[image]]

重み付きグラフに使う：

Wolfram Language code: FindPostmanTour[[image]]

多重グラフ：

Wolfram Language code: FindPostmanTour[[image]]

中国人郵便配達順路を数通り求める：

Wolfram Language code: FindPostmanTour[[image], 3]

規則を使ってグラフを指定する：

Wolfram Language code: FindPostmanTour[{1 -> 4, 4 -> 3, 4 -> 2, 2 -> 3, 3 -> 1}]

中国人郵便配達順路が存在しないグラフに対しては，FindPostmanTourは空の結果を返す：

Wolfram Language code: FindPostmanTour[[image]]

FindPostmanTourは大きいグラフに使うことができる：

Wolfram Language code: g = GridGraph[{10, 10, 10}];
Wolfram Language code: FindPostmanTour[g]//Short//Timing

アプリケーション  (3)

新聞配達少年が近所に新聞配達をする際に使うことのできる最短順路を求める：

Wolfram Language code: g = [image];
Wolfram Language code: route = First[FindPostmanTour[g]]
Wolfram Language code: Length[route]

距離の合計：

Wolfram Language code: Total[AnnotationValue[{g, #}, EdgeWeight]& /@ route]

郵便配達人が，配達にかかる時間と配達せずに歩く時間（デッドヘディング時間）を知っている場合の郵便配達に最も効率的な方法を求める：

Wolfram Language code: g = [image];

すべての道を通り，配達に使わない時間を最短にするための順路：

Wolfram Language code: route = First[FindPostmanTour[g]]

順路を示す：

Wolfram Language code: 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]]}]

合計の配達時間：

Wolfram Language code: deliverytime = Total[AnnotationValue[{g, #}, "DeliveryTime"]& /@ EdgeList[g]]
Wolfram Language code: deadheadtime = Total[AnnotationValue[{g, #}, EdgeWeight]& /@ route] - Total[AnnotationValue[{g, #}, EdgeWeight]& /@ EdgeList[g]]
Wolfram Language code: deadheadtime + deliverytime

有限状態マシンで行為の組合せを調べる：

Wolfram Language code: g = [image];

線グラフを生成する：

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

長さ2のスイッチカバー：

Wolfram Language code: Map[First, First[FindPostmanTour[%]], {2}]

特性と関係  (2)

オイラーグラフには中国人郵便配達順路が含まれる：

Wolfram Language code: g = GraphData["OctahedralGraph"]
Wolfram Language code: EulerianGraphQ[g]
Wolfram Language code: FindPostmanTour[g]

これはそのオイラー閉路と等しい：

Wolfram Language code: FindEulerianCycle[g] == %

連結グラフには中国人郵便配達順路が含まれる：

Wolfram Language code: g = Graph[{12, 23, 31, 45, 56, 64, 34}]
Wolfram Language code: {ConnectedGraphQ[g], FindPostmanTour[g]}

おもしろい例題  (1)

中国人郵便配達順路を求める：

Wolfram Language code: g = [image];
Wolfram Language code: Shallow[tour = First[FindPostmanTour[g]]]

閉路を動的にハイライトする：

Wolfram Language code: color[tours_] := {tours, tours[[All, 1]], Style[tours[[-1, 2]], Yellow]}
Wolfram Language code: Dynamic[HighlightGraph[g, color[tour[[1 ;; Clock[{1, Length[tour], 1}, 40]]]]]]
Wolfram Research (2012), FindPostmanTour, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindPostmanTour.html （2015年に更新）.

テキスト

Wolfram Research (2012), FindPostmanTour, Wolfram言語関数， https://reference.wolfram.com/language/ref/FindPostmanTour.html （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

BibTeX

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

BibLaTeX

@online{reference.wolfram_2026_findpostmantour, organization={Wolfram Research}, title={FindPostmanTour}, year={2015}, url={https://reference.wolfram.com/language/ref/FindPostmanTour.html}, note=[Accessed: 12-October-2026]}