『最短経路の本』二周目

真ん中あたりから読み始めて 23 章まで。

Euler path/circuit の話が出てきて、それが存在するための必要十分条件とその証明。この部分は数学的帰納法の解説にページ数を割いてたりするので流し読み。

次に、Euler circuit が存在しない場合に、複数回通る辺があってもいいからすべての辺を通る閉路で最短なものを求める話。次数が奇数になる点だけを取り出して、各点間の最短経路で重み付けした完全グラフを作る。その完全グラフの最小マッチングを元のグラフに加えたものの Euler circuit が求める経路になるという筋書き。無向グラフでも有向グラフでも基本的な考え方は同じ。

ここから先はあまり具体的なアルゴリズムが出てこなかったような気がするので、その部分は他の本で補う必要がありそうです。