A Mathematical Question on Maps

classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

A Mathematical Question on Maps

RogerCooper
I have been analyzing maps and creating statistics based on them. One statistic I compiled is average number of connections per territory.

My question is, what is the highest average number of connections you can get. I am assuming that all connections are between adjacent territories (no diagonal connections). Is 6 the max? Can it be proven?
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

Cernel
Interesting question.

I guess 6 should be the max, reached only by hexglobe (which is surely not representing a globe at all, by the way, but a totally flat plain). I imagine whatever other maps should have less than 6 per territory average, probably somewhere in between of 5 and 6, but closer to 6. What did you actually find out?

I duno if mixing more than 6 with less than 6 (like mixing pentagons and octagons, duno if it will work), instead of only hexes, would make for more or less connections total, in a XY map, like hexglobe.

Of course, in whatever map with no XY scrolling you lose a bunch of connections, which is the more important the less territories total you have.

The smallest XY map would be a tetragon (a 4 sided dice), which would have only 3 connections per territory (and 4 territories total).
History plays dice
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

Pulicat
According to graph theory, the answer is 6.

A TripleA map is simply an undirected graph composed of many territories each represented by a unique vertex (center), and each territory connection is represented by an edge (a line connecting the vertices). The question posed is solving for the highest average degree (edges incident to a vertex) in a graph where no edges cross each other, for which there is an Euler's formula. Given the constraints that one face must have a minimum 3 edges (min 3 terr in a neighborhood, 3 dimensions) and each edge has a maximum two faces, we can conclude that the highest average degree is 6. If it's more than 6, the graph can't be planar.

Cheers,
Puli
how now brown cow?
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

Zim Xero
In reply to this post by RogerCooper
"what is the highest average number of connections you can get"

There is no limit.  We can connect all the territories to each other.
'thats the way it is' makes it neither desireable nor inevitable
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

RogerCooper
In reply to this post by Cernel
The maps I have looked at average 5. Thanks to Pulicat for showing that 6 is the max.

Zim Xero: I specified that only adjacent areas be connected (no diagonals)

The min is 0 (a map with 1 area). An infinite map could still be as low as 2 (if the map consisted of parallel bands).
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

Zim Xero
'thats the way it is' makes it neither desireable nor inevitable
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

Pulicat
Zim,

There is no limit to the number of connections of any one territory. However, Roger was asking for the average. If you factor in all the territories of your example, you will see that the large number of connections of the big square is balanced out by all the little squares with only 2 or 3 connections. It is mathematically impossible to have a map where the average number of connections for all the territories exceeds 6, with the condition that connections are only between neighboring territories and territories are all contiguous (no exclaves).

Puli
how now brown cow?
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

Eschelon
Actually...

If your map uses a 'square grid' pattern, with kitty corner moves allowed, your average and typical number of connected territories could be 8, unless some of those territories are blocked in some fashion (wall, etc.).

Also, if you had vertical connections (say you are laying out a dungeon and have ladders between levels) you could end up with more connections than 8.

I've actually pondered making a dungeon for TripleA... too many other things to do first though!

I'd concur that the typical average falls between 5 and 6 territories, though.
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

RogerCooper
Eschelon wrote
If your map uses a 'square grid' pattern, with kitty corner moves allowed, your average and typical number of connected territories could be 8, unless some of those territories are blocked in some fashion (wall, etc.).
I had specified no diagonal connections. It is hard to march an army through an infintesmial point.
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

Zim Xero
This post was updated on .
i see, should have read the question better.  You are basically right.  It is possible to go under 2 with a non-infinite map.  I question whether you are correct on 6 limit though.  The one below has an average number of 1.5 connections.
 

I tried and failed to exceed hex capacity with the below.  However, if you draw a big circle around the outside of a hexagaon map... and count it as a territory... you exceed 6 connections per territory.  There is probably a sweet spot that gives the largest increase.  if you surround 10x10 hexes you get a bigger increase in connections than if you surround 100x100 hexes with a circle, but if you surround 5x5 hexes there are too many low connection hexagons on the outer perimeter so connection number will fall to less.

'thats the way it is' makes it neither desireable nor inevitable
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

RogerCooper
Zim Xero wrote
I tried and failed to exceed hex capacity with the below.  However, if you draw a big circle around the outside of a hexagaon map... and count it as a territory... you exceed 6 connections per territory.  There is probably a sweet spot that gives the largest increase.  if you surround 10x10 hexes you get a bigger increase in connections than if you surround 100x100 hexes with a circle, but if you surround 5x5 hexes there are too many low connection hexagons on the outer perimeter so connection number will fall to less.
The bonus from the outer circle will fall precisely as the penalty from the outer hexagons falls. 6 is the limit.
Reply | Threaded
Open this post in threaded view
|

Re: A Mathematical Question on Maps

RogerCooper
Zim Xero's map quickly approaches 6 for average number of connections

Radius=1, C=4.5
Radius=2, C=5.4
Radius=3, C=5.68
Radius=4, C=5.81
Radius=5, C=5.93