Skip to main content

Graph theory for railfans: A side story of Authors in a Markov matrix


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?
``What kind of application do you think of, if any?'', I asked him. He explained me that this is his friend's problem. His friend is working for a railway company. He needs to check all the railway track in his country regularly with a special train. How efficient he can check the railway is an important problem. This is called a Chinese postman problem in graph theory. Mei Ko Kuan, a Chinese mathematician, is one of the early researcher of this problem, so the name of the problem comes from that. This is related with the Euler path problem (one-stroke problem). Now you see the connection between graph theory and railway.

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
Kasai also explained the algorithm in details (in Japanese). He used a commercial linear programming solver, that was quite expensive in 2000. However, five years later, he revised the method and show how to solve the problem on a personal computer with a free liner programming solver, GLPK (GNU Linear Programming Kit).

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.

Labels:

Comments

Post a Comment

Popular posts from this blog

Why A^{T}A is invertible? (2) Linear Algebra

Why A^{T}A has the inverse Let me explain why A^{T}A has the inverse, if the columns of A are independent. First, if a matrix is n by n, and all the columns are independent, then this is a square full rank matrix. Therefore, there is the inverse. So, the problem is when A is a m by n, rectangle matrix.  Strang's explanation is based on null space. Null space and column space are the fundamental of the linear algebra. This explanation is simple and clear. However, when I was a University student, I did not recall the explanation of the null space in my linear algebra class. Maybe I was careless. I regret that... Explanation based on null space This explanation is based on Strang's book. Column space and null space are the main characters. Let's start with this explanation. Assume  x  where x is in the null space of A .  The matrices ( A^{T} A ) and A share the null space as the following: This means, if x is in the null space of A , x is also in the n...
Post a Comment
Read more

Gauss's quote for positive, negative, and imaginary number

Recently I watched the following great videos about imaginary numbers by Welch Labs. https://youtu.be/T647CGsuOVU?list=PLiaHhY2iBX9g6KIvZ_703G3KJXapKkNaF I like this article about naming of math by Kalid Azad. https://betterexplained.com/articles/learning-tip-idea-name/ Both articles mentioned about Gauss, who suggested to use other names of positive, negative, and imaginary numbers. Gauss wrote these names are wrong and that is one of the reason people didn't get why negative times negative is positive, or, pure positive imaginary times pure positive imaginary is negative real number. I made a few videos about explaining why -1 * -1 = +1, too. Explanation: why -1 * -1 = +1 by pattern https://youtu.be/uD7JRdAzKP8 Explanation: why -1 * -1 = +1 by climbing a mountain https://youtu.be/uD7JRdAzKP8 But actually Gauss's insight is much powerful. The original is in the Gauß, Werke, Bd. 2, S. 178 . Hätte man +1, -1, √-1) nicht positiv, negative, imaginäre (oder gar um...
Post a Comment
Read more

Why parallelogram area is |ad-bc|?

Here is my question. The area of parallelogram is the difference of these two rectangles (red rectangle - blue rectangle). This is not intuitive for me. If you also think it is not so intuitive, you might interested in my slides. I try to explain this for hight school students. Slides:  A bit intuitive (for me) explanation of area of parallelogram  (to my site, external link) . 
Post a Comment
Read more