I sometimes play with my 4 year old son with the Lego Duplo train and I realized that often our tracks have fixed points in the sense that if the train starts at a random track piece and random direction, it eventually arrives at a piece where it cannot
- traverse the same piece the other way round
- reach all other pieces from the same piece
The track consists only of standard 2-ended pieces and junctions with 3 ends ABC where AB or AC is an edge but not BC.
In order to come up with a track where the above problems do not arise, I'd like to
- formalize the track layout and find a suitable logic (which is not that easy given that AB and AC are edges and therefore BA and CA are edges but it does not follow that: BA & AC => BC, i.e., it's not transitive)
- find track layouts where each piece is reachable in either direction from every other piece/direction combination on the track. (I know that an 8 where the middle point consists of 2 connected junctions is such a track)
Up to now I have been unable to find anything formal and useful other than trivalent graphs [1] (a dead end) and penrose railway mazes [2] where the problem is just solved on images using search algorithms.
I think you are on the right track with the figure 8 configuration.
I think the two loops are what are important for traversing both directions. I would formally define this loop as follows. (Note: that since these edges are directional I am using "->" to denote these edges.)
Definition: Junction Loop
Consider an arbitrary junction K with vertices l,m,n such that l->m and l->n. This junction K will contain a loop if there exists a path that connects m->n or n->m.
------------------------------
Defintion: A Dmichulke Track
A Dmichulke Track is a track that any piece of track can be traversed in both directions and there exists a path between any two pieces of track
-------------------------------
Conjecture:
Any track will be a Dmichulke track if it has a two junctions J_1 (with vertices a,b,c such that a->b, a->c) and J_2 ( with vertices x,y,z where x->y and x->z) that satisfy the following conditions.
1) J_1 and J_2 must be have a path connecting vertex a to vertex x
2) J_1 and J_2 must contain a loop.
3) There must exist a path to either of these junctions from any point of the track.
-------------------------------
This should satisfy the stated conditions. You should play around with track configurations that satisfy these conditions and see if you can find a counter example.
This is only a conjecture though since I didn't really prove anything. I may take a crack at working on that proof over the weekend and let you know how it goes.
connecting utilities (electricity, water, natural gas) to houses. If we can keep from crossing those lines, it will be safer and easier to install.
Connecting components on a circuit board: the connections on a circuit board cannot cross. If we can connect them without resorting to another layer of traces, it will be cheaper to produce.
Subway system: if subway lines need to cross, we've got some serious engineering to do.
Also:
The study of two-dimensional images often results in problems related to
planar graphs, as does the solution of many problems on the two-dimensional surface of our earth.
Many natural three-dimensional graphs arise in scientific and engineering problems. These often
come from well-shaped meshes, which share many properties with planar graphs.
I sometimes play with my 4 year old son with the Lego Duplo train and I realized that often our tracks have fixed points in the sense that if the train starts at a random track piece and random direction, it eventually arrives at a piece where it cannot
- traverse the same piece the other way round
- reach all other pieces from the same piece
The track consists only of standard 2-ended pieces and junctions with 3 ends ABC where AB or AC is an edge but not BC.
In order to come up with a track where the above problems do not arise, I'd like to
- formalize the track layout and find a suitable logic (which is not that easy given that AB and AC are edges and therefore BA and CA are edges but it does not follow that: BA & AC => BC, i.e., it's not transitive)
- find track layouts where each piece is reachable in either direction from every other piece/direction combination on the track. (I know that an 8 where the middle point consists of 2 connected junctions is such a track)
Up to now I have been unable to find anything formal and useful other than trivalent graphs [1] (a dead end) and penrose railway mazes [2] where the problem is just solved on images using search algorithms.
[1] https://en.wikipedia.org/wiki/Cubic_graph
[2] https://demonstrations.wolfram.com/PenrosesRailwayMazes/
Can anyone help me?