紙媒体で知識や経験を管理すると無くなりがちなのでブログで管理することにしました.
      殆どの記事は自分自身のためだけに書いているため,他人に見せる前提の内容, 文章ではありません.
      また, ブログのコメント欄を解放していたらbotからの迷惑行為を受けたため現在コメント欄は解放しておりません.

【グラフ理論】 中国人郵便配達問題

中国人郵便配達問題
https://ja.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E4%BA%BA%E9%83%B5%E4%BE%BF%E9%85%8D%E9%81%94%E5%95%8F%E9%A1%8C

中国人郵便配達問題(ちゅうごくじんゆうびんはいたつもんだい、英: Chinese postman problem)とは、グラフ理論における問題の一つであり、以下のように定義される。
Gを連結な無向グラフとし、Gの各辺には距離が割り当てられている。このとき、Gの辺をすべて通るような閉路のうち、距離の合計が最小になるものを求めよ。

まずオイラーグラフGが与えられたときに, オイラー回路Wを求めるアルゴリズムは次の3つあるらしい(詳しくは勉強していない)

f:id:umashika5555:20180904000743p:plain
図: オイラー回路を求めるアルゴリズム

Gの辺をすべて通らなければならないので, (距離の合計を最小化するためには)同じ辺なんて2回通らない方がよいのは自明.
Gがオイラー回路(各点の次数が偶数)であれば, 各辺1回しか通らないため, 辺の重みの総和が答え.

オイラーグラフでないとき, 少なくとも1つの辺は2度通る必要がある.
重複する辺の重みの和は最小化した方が良い. (なぜならグラフGの辺の総和に重複分の重みを足すので重複文はできるだけ小さくしたいから)
各辺を一回しか通らないという考えのもと, 辺を重複して通るとは, 辺二重化を行ったグラフで考えれば良い.
f:id:umashika5555:20180904003011p:plain
図: 辺の二重化
上図は奇点に対して, 辺二重化をするということで, 単一の辺には一回しか通らないという原則を生み出している.

中国人郵便配達問題のアルゴリズム
(1)次の条件を満たすようにGの対象の辺を辺二重化してオイラーグラフ G^*をつくる
 [条件] G^*は辺二重化して付け足した辺の重みの総和 \sum_{e\in E(G^*)-E(G)}w(e)が最小になる
(2)  G^*オイラー回路を見つける(上記アルゴリズム)
に従っている.

中国人郵便配達問題の解き安さは下の関係になっている.
f:id:umashika5555:20180904010022p:plain
図: 中国人郵便配達問題の解きやすさの関係(大きいほど一般化された問題)
オイラーグラフであるときは, 始点と終点が一致し, 全ての辺をそれぞれ一回しか通らないので辺の重みの総和が答え.
次にオイラー小道を持つグラフのときは, 始点から終点までの最短経路を考え(ダイクストラ法), その最短経路を辺二重化することによって閉路とすることでオイラーグラフに帰着する.
f:id:umashika5555:20180904011053p:plain
図: オイラー小道を持つグラフでの中国人郵便配達問題の解き方
最後に一般の連結グラフでは, 奇点が偶数個のグラフは, 奇点全体の集合Sの任意の2点から完全グラフを作り, そこから完全マッチングな辺集合Mをつくる.(完全マッチングについてはまた今度). Mの任意の辺について対応するGの辺を二重化する. これを G^*とする.  G^*についてオイラー回路を求めて, オイラーグラフの問題に帰着させる.