中国人郵便配達問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』
中国人郵便配達問題（ちゅうごくじんゆうびんはいたつもんだい 英：Chinese postman problem）とは、グラフ理論における問題の一つであり、以下のように定義される。
Gを連結な無向グラフとし、Gの各辺には距離が割り当てられている。このとき、Gの辺をすべて通るような閉路のうち、距離の合計が最小になるものを求めよ。
目次 |
問題の考え方 [編集]
グラフにおいて、すべての辺を1度ずつ通るような閉路をオイラー路という。よってこの問題を解くには、与えられたグラフにおいて、グラフ中の一部の辺を2本に増やすことでオイラー路が得られるようにすることを考えればよい。そのような辺の組み合わせは一般に複数通りあるが、その中で増やした辺に割り当てられた距離が最小になるような辺の組み合わせを求めればよい。
与えられたグラフGがすでにオイラー路を持つ（オイラーグラフである）場合、そのオイラー路が最短の閉路であり、求める閉路の長さはGの辺の距離の総和である。一方与えられたグラフGが木である場合には、すべての辺を2本に増やさなければならず、求める閉路の長さはGの辺の距離の総和の2倍である。
解法 [編集]
名称について [編集]
この問題を研究していた中国人数学者の管梅谷(Mei Ko Kuan)にちなみ、当時アメリカ国立標準技術研究所(NIST)に所属していたAlan Goldmanが1962年に付けたものである(参照：Chinese Postman Problem)。
関連項目 [編集]
- グラフ理論
- 巡回セールスマン問題 - グラフ中のすべての頂点を通る最短の閉路を求める問題
 |
この項目は、数学に関連した書きかけの項目です。この記事を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。 |
