From: | tomhchappell <tomhchappell@...> |
---|---|

Date: | Tuesday, January 31, 2006, 18:03 |

--- In conlang@yahoogroups.com, Sai Emrys <sai@S...> wrote:>Arbitrary in my use: any node can be connected to any number of >other nodes. (assuming it's on the node-and-connection sort of >style, which it need not be if it has a fusional morphology)Well, the problem is with the two uses of the word "any". Here are the rules that matter; If: 1) Each tile ("node") has exactly the same limitations as each other tile; and, 2) Two tiles are "connected" exactly if they share some portion of an edge; and, 3) No two tiles are allowed to overlap each other; and, 4) The whole layout must occur on a _flat_ surface: Then: Each tile can be "connected" to at most six other tiles. If, instead, you use vertices for nodes and lines for connections, rules 2 and 3 will be represented by the requirements that lines cannot cross one another, nor run through nodes. --- However, it is a fact that, for any given "n", the layout could contain arbitrarily many tiles (or nodes) which were connected to "n" other neighboring tiles; its just that, if n>6, some (at least n-6, if I am not mistaken) of the neighboring tiles would have to be of a different sort (limited to fewer-than-n neighbors). As an example, you could tile the plane with regular dodecagons (12- gons) and equilateral triangles, such that each dodecagon had twelve (12) neighbors; six (6) other dodecagons, and six (6) triangles. Each triangle would have three (3) neighbors, all of which were dodecagons. Not _any_ node, in this example, can have more than six neighbors; the triangles can't have more than three. But there can be arbitrarily many nodes that have up to twelve neighbors; its just that at most six of those neighbors can also have up to twelve neighbors.>I still don't see how you can say it's 6. Could you please show me >the math?Not me; sorry. I know the math has been done, but I think Jeff Wilson, or someone else, will have a better chance of showing it to you than I will.>I'm not sure about cases where 'neighbors' are directly touching, >but it's obviously false if they can be simply connected by lines. >E.g.: >[paste this into a notepad w/ an equal-width font] > 1 2 3 > \|/ > 4-O-5 > /|\ > 6 7 8 > ... and that's not even using multiple 'layers', or variable length > connecting lines, branching ones, or anything like that.(Well, actually, if the numbered nodes have many further connections, these connecting lines probably are variable length, in that 1-O, 3- O, 6-O, and 8-O can't all be the same length as all of 2-O, 4-O, 5-O, and 7-O.) The problem is that a _regular_, _planar_ graph can't have the degrees of all its nodes greater than 6. It is taken for granted in graphs that two nodes can't be (directly) connected to each other by more than one (direct) connection; and that no connection connects more than two nodes to each other; and that no connection connects any node to itself. A graph is "regular" if every node has just as many connections as every other node. A graph is "planar" if it can fit on a plane without any of the connections crossing each other. It turns out that a graph is planar exactly if it does not contain any graphs that look like either of the following two graphs: 1) A complete 5-vertex graph (that is, five nodes each of which is connected to each of the other four nodes); 2) A "utilities graph" (two sets of three nodes, where each node in each set is connected to all three of the nodes in the other set). ----- Let me give three examples. Example THC1; .-.-.-.-.-.-. .\|/|\|/|\|/. .-A-B-C-D-E-. ./|\|/|\|/|\. .-F-G-H-I-J-. .\|/|\|/|\|/. .-K-L-M-N-O-. ./|\|/|\|/|\. .-P-Q-R-S-T-. .\|/|\|/|\|/. .-U-V-W-X-Y-. ./|\|/|\|/|\. .-.-.-.-.-.-. Note that A, C, E, G, I, K, M, O, Q, S, U, W, and Y are all different from B, D, F, H, J, L, N, P, R, T, V, and X. M, G, I, Q, and S, for instance, have eight neighbors each; but H, L, N, and R, for instance, have only four neighbors each. This is not a "regular" graph; that is, it is not the case that every vertex has the same number of neighbors as every other vertex. The degree-4 nodes, for instance H, cannot acquire connections to the closest nodes that they aren't already connected to, (in H's case, to B, D, L, or N), without having some other connection broken, or having the lines cross. For instance, if H gets connected to L, that crosses the connection from G to M; if H gets connected to N, that crosses the connection from I to M. Also note that M, for instance, _cannot_ acquire a connection to any of A, B, C, D, E, F, K, P, U, J, O, T, Y, V, W, or X, unless some other connection is broken, unless the connecting lines are allowed to cross each other. This example is like my octagon-and-diamond "bathroom floor" tiling example I gave in an earlier post. -- Example THC2; .-.-.-.-.-.-. .\|\|\|\|\|\. .-A-B-C-D-E-. .\|\|\|\|\|\. .-F-G-H-I-J-. .\|\|\|\|\|\. .-K-L-M-N-O-. .\|\|\|\|\|\. .-P-Q-R-S-T-. .\|\|\|\|\|\. .-U-V-W-X-Y-. .\|\|\|\|\|\. .-.-.-.-.-.-. Example THC3; .-.-.-.-.-.-. ./|/|/|/|/|/. .-A-B-C-D-E-. ./|/|/|/|/|/. .-F-G-H-I-J-. ./|/|/|/|/|/. .-K-L-M-N-O-. ./|/|/|/|/|/. .-P-Q-R-S-T-. ./|/|/|/|/|/. .-U-V-W-X-Y-. ./|/|/|/|/|/. .-.-.-.-.-.-. Each of these two examples is like a hexagonal tiling. In both of them, every node has exactly six neighbors. Again, no node can pick up a new connection without either; 1) leaving the plane, or 2) having two connections cross each other, or 3) severing an old connection. For instance, in THC2, node M can't be connected to either of nodes I or Q, because an M-I connection would cross the H-N connextion, and an M-Q connection would cross the R-L connection. And, in THC2, node M can't be connected to either of nodes G or S, because an M-G connection would cross the H-L connection, and an M-S connections would cross the N-R connection. In neither example can we add any of the following connections; G-N, G-R, H-Q, H-S, I-L, I-R, L-S, N-Q; because any of them would cross one of the connections H-M, L-M, M-N, or M-R. --- I hope that helps. Tom H.C. in MI

Jim Henry <jimhenry1973@...> |