not so easy math problem

Talk about anything not related to Transcendence.
Post Reply
User avatar
Betelgeuse
Fleet Officer
Fleet Officer
Posts: 1920
Joined: Sun Mar 05, 2006 6:31 am

other than brute force are there any math ways of going at this problem?

all vertexes have a level

there are at most maxVertexesPerLevel vertexes per level

not vertex can have a level below 1 or above maxLevel

all vertexes have a random number of edges connecting to it up to maxEdges

there is a w% chance that an edge will connect to a vertex of the same level
there is a x% chance that an edge will connect to a vertex of the 1 lower level
there is a y% chance that an edge will connect to a vertex of the 1 higher level
there is a k% chance that an edge will connect to a vertex of the 2 lower level
there is a j% chance that an edge will connect to a vertex of the 2 higher level

you start with a level one vertex and whatever it has an edge to also is a valid vertex with edges of its own

ok now that the assumptions are out of the way here are the questions

What I am interested in is two things the number of vertexes and the level of the highest level vertex (it doesn't have to be maxLevel).

How does maxVertexesPerLevel, w, x, y, k, j, maxEdges effect them?
The reason I ask is because I don't know how to do these kind of problems other than brute force and would like a better way of influencing the graph.
Crying is not a proper retort!
User avatar
Betelgeuse
Fleet Officer
Fleet Officer
Posts: 1920
Joined: Sun Mar 05, 2006 6:31 am

hmm one way to make sure is just add an extra edge if the level's edges are filled up and there are no nodes above this level
Crying is not a proper retort!
User avatar
digdug
Fleet Admiral
Fleet Admiral
Posts: 2620
Joined: Mon Oct 29, 2007 9:23 pm
Location: Decoding hieroglyphics on Tan-Ru-Dorem

mmmhh, if maxEdges =2 ( a semplification, I know) meaning that you are only passing through an unique vertex only 1 time (like you are constructing a path), you have the so called "shortest path problem" that has been analyzed deeply in the last decades.

http://en.wikipedia.org/wiki/Shortest_path_problem

There are a number of algorithms that calculates these paths.
schilcote
Militia Captain
Militia Captain
Posts: 726
Joined: Sat Feb 02, 2008 7:22 pm

Clickety clackClickety clackClickety clackClickety clack
(overheats)
BOOM...
[schilcote] It doesn't have to be good, it just has to not be "wow is that the only thing you could think of" bad
Sideyr
Anarchist
Anarchist
Posts: 6
Joined: Sun Sep 07, 2008 2:19 am
Location: Los Angeles, CA

Being something of a math geek, I can't pass up a message title of this sort, but I'm afraid you'll need to define your question a bit better. Given what you've asked, I can extrapolate a bit, though:

1) Probabilities are irrelevant when you ask a question that isn't about the probability of some outcome, aside from whether they are non-zero. So I'll have to assume that you're asking a question about the probability of various resulting graph topologies, given the inputs.

2) I'll also have to make some assumptions about probabilities you haven't specified, such as what the probability distribution is for choosing e edges out of the possible range 1 to maxEdges. I'll assume you mean to use a uniform probability distribution with a 1/maxEdges probability of choosing each possible number of edges between 1 and maxEdges. 0 edges is technically possible for the very first vertex, but isn't very interesting. Other vertexes obviously have to have at least their incoming edge.

3) I'd still need to know what your algorithm is for adding a new edge to the graph at each step, however, and I'd have to go farther out on a limb to guess your intentions, so I'd say I can't safely go any further at this point.

So, I'll ask some questions to narrow it down:

1) Are you building a tree or a graph?

1a) A tree has branches, but no loops, and would be constructed by always adding a new vertex connected to an existing vertex with an available edge at each step. Aside from correcting the assumptions I've made above, I think there's enough information to generate some answers if this is your goal.

1b) A graph can contain loops, and would involve another step in building to choose whether to build a bridge between two existing vertices which each have a free edge or to build a branch to a new vertex, at each step. To answer any questions about this sort of construction, you'd also need to define a probability that you'd add a bridge vs. a branch at each step.

I can guess, given where you've posted this, that you might be trying to randomly generate an interstellar gate network topology, in which your vertexes are star systems and edges are gate connections.

As an astronomy and physics geek, I hope you'll forgive me if I possibly follow this thread off topic:

A branching tree might be reasonable if the ancient builder race's gate technology (or security concerns) placed limitations on the distance between endpoints (otherwise, they would just have built a hub system connecting every other system to their home system to minimize the number of hops between), and if interstellar gates were expensive enough to the ancient builder race that minimizing the number overruled any concerns about redundancy (otherwise, they would probably have wanted a graph with loops so that losing a gate wouldn't cripple the network). A graph is the best solution if gates weren't prohibitively expensive, but were distance limited.

If I were going to build a sensible gate network in this situation, I think I'd actually go about it by positing the building conditions. I.e. assume a 3D distribution of star systems by sprinkling around a bunch of 'important'
stars constrained in a galaxy-like distribution, then connect the dots wherever they are close enough and there aren't other short enough connecting routes through the graph. 'Important' stars are probably life-sustaining or resource-rich, plus some strategic locations perhaps where no useful stars are close enough to be directly connected by gates. Of course, we'd have to make assumptions about whether 'life-sustaining' meant the same thing to the ancients as to humans. For a 'galaxy-like' distribution, the Milky-Way more or less consists of a disk ~3-600 light years thick and ~60,000 light years in radius, with a bulge ~6,000 light years in radius at the middle. The spiral arm density waves in the disk are fairly irregular but are maybe ~10-20,000 light years wide and are probably the most likely location for life and star faring races, as they are composed of younger stars that have seen many generations of metal-enriching star birth. There's also a big very diffuse halo of old stars ~65,000 light years in radius, and a number of clusters of stars orbiting the galaxy (including the Magellenic clouds), but these are generally pretty metal-poor stars. The bulge is very crowded with old red stars, though not so metal-poor, and so probably isn't an ideal place for a race to evolve, though it might be interesting to explore for a star travelling race. The crazy whirling death machine of a black hole that almost certainly sits in the center might also attract a technologically advanced enough race.

Err... please forgive me if I've bored everyone to death at this point...
Post Reply