中国人郵便配達問題

中国人郵便配達問題（ちゅうごくじんゆうびんはいたつもんだい、英: Guan's route problem, Chinese postman problem）とは、グラフ理論における問題の一つであり、以下のように定義される^[1][2]。

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

解法

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

オイラーグラフの特徴として「すべての頂点の次数（頂点に接続する辺の数）は偶数である」ことが挙げられる。一般の（次数が奇数である頂点を持ちうる）グラフに対しては、以下の方法に基づいてグラフ中の一部の辺を2本に増やせばオイラーグラフになる^[1]。

1. グラフ中に存在する、次数が奇数であるすべての頂点を集める。なおその頂点数は「握手補題」により必ず偶数個になる。
2. 上記の頂点を適当に二つずつ組み合わせる。
3. この組のそれぞれについて、「最短経路を見つけ、その辺をそれぞれ1本増やす」ことを行う。

よって中国人郵便配達問題は、上記の手順2における頂点を二つずつ組み合わせる方法のうち、手順3にて増やす辺の距離を最小にするようなものを求める問題（最小マッチング）に帰着される^[1]。この最小マッチングは${\displaystyle O(V^{3})}$時間で求められることが知られている（ただし、そのアルゴリズムは難しいものである）^[3]。他の処理も${\displaystyle O(V^{3})}$時間以内で行えるため（全頂点組に対する最短経路を見つけることはワーシャル-フロイド法により${\displaystyle O(V^{3})}$時間で可能）、全体の時間計算量も${\displaystyle O(V^{3})}$となる^[1]。ただし、${\displaystyle V}$は頂点の数である。

自明な例

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

名称について

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