I'm having fun with GraphViz

[Pumpkin]

Btw, the word you were looking for is connectedness.

Thanks a lot!

I (...) could not get what you are trying to prove.

I was trying to prove that my way to build a fully connected graph ("in one piece") actually and always makes a fully connected graph.

That way was:
1) start with a graph of 1 vertex;
2) each time you add a new vertex, link it at least once with a previously existing vertex.

The proof this method always produce a fully connected graph is recursive:

1) If all previous planets are "in one piece" (alternatively: if all following planets will be "in one piece"), then linking the current planet to any of them at least once will keep the graph "in one piece".
2) The first planet alone is a graph "in one piece" (alternatively: the last planet will be a graph "in one piece").
3) If the first (alternatively: last) state respect the property ("in one piece"), and each step applied to a state where the property is respected keep the property true, then the property will always be true even after an infinite number of steps.

Did that answer your question? Or haven't I understood the question?

[tombik]

https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Connected_graph

This will definitely help you to come up with the definition which you will need for your argument.

The "rule" you defined there is not exactly a rule. I had some problems with your approach.

For example, In 3, you say "alternatively last" after an infinite number of steps, which is a bit problematic.

In 2, you say a single point is a connected graph, but for an algorithm, you dont need this. Just produce any two connected nodes, and build upon it.

First one just says this: "You can't make a connected graph not connected by adding new vertexes." This is trivially true already.

I dont know about GraphViz, so I dont know what exactly you need, but if I were to code these things, I would just produce a fully connected graph with every possible vertex included, and erase the vertices one by one.

[Pumpkin]

Woah, okay, things just get out of my hands. Sorry about the confusion I created. I was far from expecting such a precise answer with my little messy-funny math-thingy.

First and foremost, I'm totally fine: I'm not trying hard to achieve anything and I need nothing for my script code. I was just having fun trying to come up with a mathematical proof that this algorithm works (actually creates a connected graph).

For example, In 3, you say "alternatively last" after an infinite number of steps, which is a bit problematic.

Yeah, sure. Forget "infinite", just "any number of step", cause, sure, you need a "last" step of course.

First one just says this: "You can't make a connected graph not connected by adding new vertexes."

That's a very concise definition, indeed. GG to you.

This is trivially true already.

That, however, is personal. While I totally agree with it, I don't feel getting away with "bah, it's trivial" is a good attitude. Well, being AIW players, we can't be put off by the perspective of challenge, can we?
But, yeah. Your oneliner is good. I would just be a little more nitpicking (I think it's only fair ) and add "... by adding one new vertex linked to at least one other (previously created so part of the connected graph) vertex". Then, by adding multiple vertices, one at a time, each respecting this condition, the graph will still be connected after an infinite any number of steps added vertices. (Because, clearly, I can add multiple vertices to a connected graph that would produce a non-connected graph: by putting them aside, linked with no vertices.)

if I were to code these things, I would just produce a fully connected graph with every possible vertex included, and erase the vertices one by one.

Did you meant "with every possible edges included, and erase edges one by one"? Because there is no "every possible vertices" (at least it doesn't seem to be a finite number).
Even so, would you check if the graph is still connected after each edge removal, and step back if it's not any more? That sounds like a lot of computational overhead. And how would you stop? When reaching a target number of edges?
I don't understand that last sentence. Would you explain it further, please?

[tombik]

Did you meant "with every possible edges included, and erase edges one by one"? Because there is no "every possible vertices" (at least it doesn't seem to be a finite number).
Even so, would you check if the graph is still connected after each edge removal, and step back if it's not any more? That sounds like a lot of computational overhead. And how would you stop? When reaching a target number of edges?
I don't understand that last sentence. Would you explain it further, please?

Yes, a fully connected graph means that. For a constant number of nodes, number of possible vertices is finite, and it is combinatorial of n with 2. And yes, you need a control code for connectedness, and yes, you can define it after "k" erasings or something.

But after a second thought, I dont think my way is superior than your way. It really depends on what you are trying to achieve, and in maps for AIW, your way would be superior. Sorry about that.

Here is how to deal with connectedness. You should use some search algorithms to check that whether you can reach every possible point. To do this, you need to "color" them, like "visited but not all neighbours visited" "not visited" "visited, and all neighbours are visited". If for any step, you are in a position where every visited one has also their neighbours visited, but there are also some unvisited ones, then the graph is unconnected.

Other way to deal with the connectedness is to extract adjacency matrix. This matrix just consists of 0s and 1s, and shows that whether there is any direct link between the relevant column (ith point) and relevant row (jth point). First degree of this shows all connected points of course. If you take square of it, you will get positive values for all two points that could be reached by going two steps. If you take cube of this matrix, you will get positive values in the cells that represent points that could be reached via 3 steps. And so on. So, if you check adjacency matrix's power up to number of nodes, and find that there are some zeros in some specific cells in each of those powers, then this means, there are some points that cant be reached from one to other no matter how many steps you are using, and that means graph is unconnected.

I hope that helps.

[Pumpkin]

At least one of us is wrong on the use of the word "vertex". I believe vertex = node, and not vertex = edge.

Anyway, your way of checking the connectiveness of a graph with the successive powers of a matrix is very interesting.

However my goal was to create scripts that build connected graphs without the need of connectiveness checking. Hence the little proof. I believe even that smart matrix thing is a bit CPU-expensive. But maybe I'm wrong and with that it wouldn't be a problem checking connectiveness even once per removed edge.

Anyway, making scripts that always produce connected graph without the need of checking is a very interesting challenge.

[tombik]

At least one of us is wrong on the use of the word "vertex". I believe vertex = node, and not vertex = edge.

Anyway, your way of checking the connectiveness of a graph with the successive powers of a matrix is very interesting.

However my goal was to create scripts that build connected graphs without the need of connectiveness checking. Hence the little proof. I believe even that smart matrix thing is a bit CPU-expensive. But maybe I'm wrong and with that it wouldn't be a problem checking connectiveness even once per removed edge.

Anyway, making scripts that always produce connected graph without the need of checking is a very interesting challenge.

You are the one that uses it correctly, I just checked.

I see what you are trying to achieve, but if you dont go with some randomness, every algorithm which you try to write would produce look alike maps, that is why I tried to convince you that some connectedness checking is required.

Anyways, here is an algorithm that will give you the thing you want.

1) Draw two points, and connect them. Name the set of connected points as P.
2) Draw an additional point. Connect it to some random member of P. After connection, include this point in P.
3) Repeat step 2 as many times as you wanted.
4) If you want more ways to go from one point to the other, you can add just some random edges between the points.

[Draco18s]

You may also be interested in Minimal Spanning Trees.

[Pumpkin]

You may also be interested in Minimal Spanning Trees.

Sure. However trees are only one kind of map (and not the most interesting, IMO). I'm personally more interested in exotic map design.

However, there are very cool things in the field of graph theory, even if they're not interesting for the very particular AIW's map generation.

[Draco18s]

Sure. However trees are only one kind of map (and not the most interesting, IMO). I'm personally more interested in exotic map design.

Ah, but you can start with a MST and then modify it, adding extra random links, etc.

[Pumpkin]

Oh, I was just thinking about a little idea about AIW2, so I write it down here.

I think it would be nice to have "statistics" about the currently displayed galaxy in the lobby, like the exact number of planets, the total number of wormholes (number of edges x2) and the average number of wormholes per planet (nb_wormhole/nb_planets). I can't think of other interesting stats to display about graph; my math knowledge ends here. Someone?