This is a side story of ``Authors in a Markov matrix: Which author inspires the people most?'' What relationship do railfans and Graph theory have? is the theme of this story. (Japanese version)

My colleague Dietger asked me, ``Do you know how to traverse the all the edges in a graph?'' I asked back, ``Isn't it a Hamiltonian path problem?''

He answered, ``No. Hamiltonian path is the problem to traverse all the nodes only once. Instead of the nodes, I want to know how to visiting all the edges once.'' I intuitively answered, ``Can we solve it on the dual graph?'' But this was wrong. Figures 1, 2, 3 show the what is the face-vertex dual graph, and Figure 3 shows there is no edge dual graph. For instance, in a triangle mesh, vertices are connected via edges, faces are also connected via edges. Therefore, vertex (node) and face can be (so called) dual. Then, what is the connection between edges? There is no connection between edges, or edges themselves are connection. This is the difference between face/vertex and edge.

Figure 1: Duality of face and vertex: faces to a dual graph. |

Figure 2: Duality of face and vertex: a dual graph to faces. |

Figure 3: Edge's duality? |

I recall a similar problem that was presented at PTT (Programming tools and techniques) long time ago. PTT is a kind of club that the people are interested in computer programming. In some reason, there are many railfans also. Kasai presented ``Longest One-way-ticket Problem'' at PTT. ``Longest Oneway-ticket Problem'' is a problem to find the longest one way ticket you can buy. He thought about the JR (Japan Railway) ticket. http://www.swa.gr.jp/lop/index.html

Kasai tried two different methods: linear programming and brute-force method. The both solution are the same. But, he needed some techniques to simplify the problem for the brute-forth method, e.g., graph simplification and graph subdivision. The result is shown here. http://www.swa.gr.jp/lop/lop_res.html

referred from http://www.swa.gr.jp/lop/lop_res.html |

I am also surprised that a person compute this longest one way ticket by hand, he started this hobby around 1960s. His hand computed result is quite similar with Kasai's result. Is this person a genius, or human brain has such a incredible ability? I am impressed.

By the way, I believe railfans are all over the world. There is a special TV channel for railfans in Germany. I wonder that the German channel tried such kind of experience. Kasai used Japanese geographic constraint to simplify the graph. He divided whole Japan graph to sub-graphs since Japan is consists of islands. The connection between islands are very limited. Has anyone computed the German longest one way ticket? Or European longest one way ticket? If you know such page, please write me a comment.

## No comments:

Post a Comment