Solving Train Network Traps: Graph Theory Resources

[Ibix]

My son has a wooden train set. It has straight tracks, curves, and points. I've been [strike]playing with it[/strike]building tracks for him, and came across something odd. If I don't really think about it and just throw something together, it almost always seems to end up that there is a "trap" - a section of track that you cannot get back out of without backing up.

I am not sure of the correct terminology, so I describe a set of points as a Y with two "arms" and one "leg". Entering from the leg you can choose either arm; entering from either arm you must exit via the leg. For an example of a "trap", consider a set of points with one arm of the Y connected to some network, and the other arm connected to the leg. If you enter the points from the network, you are stuck on the loop unless you back up.

I have two questions:
1 - is my experience that networks with traps are more common representative, or am I a klutz?
2 - what do I need to read up on to understand what's going on?

I tried enumeration to answer (1), but the number of possible networks gets large fast. There are 2 with no sets of points (a straight line and a loop), 3 with one set of points (an open Y, a loop with a siding, and a return-to-sender), and I think I counted 17 with two sets of points (although I may have been double counting something - even a taxonomy for networks would be helpful!). My son's set has five sets of points...

I guess the answer to (2) is graph theory - are there any recommended resources? And is there a particular branch (see what I did there?) that I should be particularly looking at?

 

[mfb]

You can represent your network as mathematical graph, but I am not sure about the best way to keep the "direction" information.

Apart from that, there is a simple concept without a trap: a figure-8 layout with two "Y" elements, and no attached trap.

 

[willem2]

If the number of points is odd, there has to be a trap.

Your network corresponds to a graph, the points to vertices with degree 3, and a trap to a vertex with degree 1. The other rails are the edges. Since sum of the degrees of all vertices of any graph is always even (see http://en.wikipedia.org/wiki/Handshaking_lemma), there has to be an even number of vertices of odd degree, so If there is an odd number of points, there has to be an odd number of traps as well.

 

[Ibix]

Thank you both.

Willem: yes, but a even number of nodes is not sufficient to avoid traps. For example, take two sets of points and connect the leg to an arm on each, then connect up the free arms. This gives two loops connected by a line. Depending which way you set the train going, one or other loop is a trap.

 

[mfb]

A network has a trap if and only if there is a closed loop where all Y parts have the same orientation (relative to the loop).

Even without a trap, a network can have larger areas where you still have a choice, but cannot leave this area.

I found a possible representation of a network as graph (using lines as 2 nodes (one for each direction) and Y parts as vertices), but that has some redundancy in its layout, so there might be a better representation.