中国人郵便配達問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 中国人郵便配達問題の意味・解説 

中国人郵便配達問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/03/14 06:13 UTC 版)

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

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

解法

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

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

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

よって中国人郵便配達問題は、上記の手順2における頂点を二つずつ組み合わせる方法のうち、手順3にて増やす辺の距離を最小にするようなものを求める問題(最小マッチング)に帰着される[1]。この最小マッチングは

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めていますプロジェクト:数学Portal:数学)。




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「中国人郵便配達問題」の関連用語

中国人郵便配達問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



中国人郵便配達問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの中国人郵便配達問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS