この話は マルコフ行列の中の著者達の番外編である．鉄道ファンとグラフ理論の関係は何かという話である． (English version)
同僚の Dietger がグラフの全ての edge をたどる問題を知っているかと聞くので，Hamiltonian path のことかと答えると，Hamiltonian path は全ての nodeを一度通るもので，そうではなく全ての edge を通るものだということだった．
私はVertex と Edge の Dual を考えれば良いではないかと言ったのだが，Triangle mesh ではVertex と Face は Dual になるが，Edge はそうではない．(図1, 2, 3)考えてみると，点は辺を介して接続され，面も辺を介して接続されている．では辺は何を介して接続されているのだろうか．面か点である．面と点の接続関係は辺によるものなので，辺はある意味この面・点とは異なる．だから面と点を入れかえることはまだできるが，辺は何かと入れかえられないと考えた．
 |
| Figure 1: Duality of face and vertex: faces to a dual grah. |
 |
| Figure 2: Duality of face and vertex: a dual graph to faces. |
 |
| Figure 3: Edge's duality? |
これはどんな問題を考えているのかと尋ねたところ，彼の友人は鉄道の線路の管理をしているということであった．つまり線路を定期的に全て検査しなくてはならない．効率良く線路を全てまわるのはどうすれば良いのかという問題をグラフの問題として考えたものである．結局，これは中国人の郵便配達問題と呼ばれていることがわかった．中国人の数学者(Mei Ko Kuan)がこの問題に関して研究していたことにちなむらしい．これは Euler path 問題，つまり一筆書き問題とかかわりが深い．
私は昔，PTT (Programming tools and techniques) という集まりでこれに類する話を聞いたことがある．この会はソフトウェア関係の会であるが，鉄道好きの人も多数いらした．葛西さんという方が，この会で発表したのは，最長の片道切符はどんなものかというものであった．これは JR (Japan Railway) で買うことができる最長の切符である．http://www.swa.gr.jp/lop/index.html
 |
| referred from http://www.swa.gr.jp/lop/lop_res.html |
葛西氏は日本語ではあるが，アルゴリズムに関しても詳しく説明されている．2000年当時，彼の使った線形計画法のソフトウェアは商用の高価なものであったが，2005 年には計算機の性能の向上，そして，GLPK (GNU Linear Programming Kit) の登場によって家庭でもこのような計算が可能になっているそうである．その方法も示されている．
驚くことに1960年頃から手計算で片道切符の旅に取り組んでいる方がいらして，その方の経路はほとんどこの計算結果と同じというのも驚いた．人間の脳がすごいのか，この人が特殊なのか，とにかくすごいことである．
ところで，世界には鉄道ファンは多数いるはずである．ドイツにも鉄道ファンのテレビがあると聞く．そういう番組では，きっとこのような試みがあるであろう．多分．しかし，日本は地理的条件からグラフの分割というものが可能である．(グラフ的には島を結ぶ辺が極端に少ないので，葛西氏はこれを利用して計算量を減らしている．)ドイツの鉄道の最長片道切符，あるいはヨーロッパの最長片道切符はどういうものか，ご存知の方は御一報下さい．
Comments
Post a Comment