Print

Print


--- In [log in to unmask], 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