書記が数学やるだけ#620 オイラーグラフ

全ての辺を1度だけ通ることのできるグラフの性質について。

問題

説明

ケーニヒスベルクの七つの橋問題は一筆書きの代表例であり，オイラーにより解決された。オイラーグラフは全ての辺を1度だけ通ることのできるグラフである。

中国人郵便配達問題は，グラフの辺をすべて通るような閉路で重み最小のものを求める問題で，中国人数学者の管梅谷にちなみAlan Goldmanが1962年に名称を付けたとされる。

解答

オイラーグラフであることの必要十分条件として，頂点が全て偶点であることが知られている。

このことから，オイラーグラフである完全グラフや完全二部グラフの条件が絞れる。

中国人郵便配達問題について，オイラーグラフであればその閉路が答えである。

もし準オイラーグラフであれば，奇点同士を結ぶ最短距離を1本増やすことで解くことができる。なお，一般には最短距離を求めるには最小マッチングを求める必要がある。

本記事のもくじはこちら：