中国人郵便配達問題のソースを表示

'''中国人郵便配達問題'''（ちゅうごくじんゆうびんはいたつもんだい、{{Lang-en-short|Guan's route problem, Chinese postman problem}}）とは、[[グラフ理論]]における問題の一つであり、以下のように定義される<ref name="EncyclopediaOR">{{Citation|author=Saul I. Gass|author2=Carl M. Harris|author3=森村英典（監訳）|author4=[[刀根薫]]（監訳）|author5=[[伊理正夫]]（監訳）|year=1999|title=経営科学OR用語大事典|publisher=[[朝倉書店]]|isbn=4254121318}}</ref><ref name="nist">{{cite web|url=http://xlinux.nist.gov/dads//HTML/chinesePostman.html|title=Chinese postman problem|work=Dictionary of Algorithms and Data Structures|publisher=[[アメリカ国立標準技術研究所]]|accessdate=2015-02-03}}</ref>。

{{Quote|Gを[[連結グラフ|連結]]な無向グラフとし、Gの各辺には距離が割り当てられている。このとき、Gの辺をすべて通るような[[閉路]]のうち、距離の合計が最小になるものを求めよ。}}

== 解法 ==
グラフ理論において、グラフ中のすべての辺を1度ずつ通るような閉路が存在するグラフを「オイラーグラフ」といい、その閉路を「[[オイラー路]]」という。よってこの問題を解くには、与えられたグラフにおいて、グラフ中の一部の辺を2本に増やすことで、オイラーグラフが得られるようにすることを考えればよい。そのような辺の組み合わせは一般に複数通りあるため、その中で増やした辺に割り当てられた距離が最小になるような辺の組み合わせを求めることになる。

オイラーグラフの特徴として「すべての頂点の次数（頂点に接続する辺の数）は偶数である」ことが挙げられる。一般の（次数が奇数である頂点を持ちうる）グラフに対しては、以下の方法に基づいてグラフ中の一部の辺を2本に増やせばオイラーグラフになる<ref name="EncyclopediaOR" />。
# グラフ中に存在する、次数が奇数であるすべての頂点を集める。なおその頂点数は「[[次数 (グラフ理論)#握手補題|握手補題]]」により必ず偶数個になる。
# 上記の頂点を適当に二つずつ組み合わせる。
# この組のそれぞれについて、「最短経路を見つけ、その辺をそれぞれ1本増やす」ことを行う。
よって中国人郵便配達問題は、上記の手順2における頂点を二つずつ組み合わせる方法のうち、手順3にて増やす辺の距離を最小にするようなものを求める問題（最小マッチング）に帰着される<ref name="EncyclopediaOR" />。この最小マッチングは<math>O(V^3)</math>時間で求められることが知られている（ただし、そのアルゴリズムは難しいものである）<ref>{{Citation|author=Bernhard Korte|author2=Jens Vygen|author3=浅野孝夫（訳）|author4=浅野泰仁（訳）|author5=小野孝男（訳）|author6=平田富夫（訳）|year=2005|title=組合せ最適化―理論とアルゴリズム|publisher=[[シュプリンガー・ジャパン|シュプリンガー・フェアラーク東京]]|isbn=9784431711834}}</ref>。他の処理も<math>O(V^3)</math>時間以内で行えるため（全頂点組に対する最短経路を見つけることは[[ワーシャル-フロイド法]]により<math>O(V^3)</math>時間で可能）、全体の時間計算量も<math>O(V^3)</math>となる<ref name="EncyclopediaOR" />。ただし、<math>V</math>は頂点の数である。

== 自明な例 ==
* 与えられたグラフGがオイラーグラフである場合は、求める閉路の長さはGの辺の距離の総和である（そのオイラー路自体が条件を満たしている）。
* 与えられたグラフGが[[木 (数学)|木]]である場合には、すべての辺を2本に増やさなければならず、求める閉路の長さはGの辺の距離の総和の2倍である。

== 名称について ==
この問題を研究していた中国人数学者の管梅谷（Mei Ko Kuan）にちなみ、当時[[アメリカ国立標準技術研究所]]（NIST）に所属していたAlan Goldmanが1962年に付けたものである<ref name="nist" />。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
*[[グラフ理論]]
*[[巡回セールスマン問題]] - グラフ中の全ての'''頂点'''を通り、始点に帰ってくる最短閉路を求める問題
*[[最短経路問題]] - 最短経路を求める問題

{{math-stub}}

{{DEFAULTSORT:ちゆうこくしんゆうひんはいたつもんたい}}
[[Category:グラフ理論]]
[[Category:数学に関する記事]]
[[Category:組合せ最適化]]
[[Category:数学の問題]]