I’m working on a computer game in which the spaces that players can occupy are connected to other spaces by exactly three pathways, always. I wrote a quick-and-dirty program which does lots of brute-force random connections among N spaces and averages the results to tell me how “far away” two spaces can be from one another given N spaces, but I was wondering if this had already been determined, in terms of the number of different arrangements possible.
So, given a number (N) of spaces (S), each of which must have three pathways § connecting to different other S (in other words, S[sub]A[/sub] cannot connect to S[sub]B[/sub] via more than one P), how many three-dimensionally, topologically different arrangements of Ss and Ps are possible? Is there already a formula with the answer?
What I know so far is that N must always be an even number to satisfy the “exactly 3 P from each S, no duplicates” requirement, N must be at least 4, and that if N is 4, the only possible arrangement is one in which each S is at the tip of a tetrehedron, each P being an edge. After scratching for a while with paper and pencil, I’m fairly certain that if N is 6, there is also only one configuration (imagine two triangles floating parallel to each other, their vertices connected by 3 more Ps). If N is 8, I think the number of possibilities is more than 1, but I’m not quite sure. And if N is 10, I’m pretty sure there’s more than one configuration which works, but I don’t have a clue as to how many configurations there really are (2? 3? More?).
This is mostly asked in curiosity, right now, since I can continue to brute-force random networks of Ss and Ps to my heart’s content. But I was thinking about this because I thought it might be interesting to make sure that getting from one particular S to another would take at least X pathways, and was wondering how much N would need to be to force a minimum traverse of X Ps.
Yeah, the question is, given N Ss, what is the maximum mininum number of Ps which must be traversed between two Ss (let’s call this value M), given an optimally “tight” arrangement of Ss and Ps? By “tight” I mean “minimizing the value of M,” since it’s fairly obvious that it’s easy to maximize M by arranging the Ss and Ps for a high-N network…
Oh, my brute-force program came up with an “answer” of M=16 when N=2000, if that helps at all. Of course, it came up with M=15 for N=1990, but M=16 again for something like N=1970, too, so the random-brute-force-and-averaging method doesn’t exactly “work” in any deterministic sort of sense, which is what I’m looking for.