Clash Royale CLAN TAG#URR8PPP

python generate random connected graph with certain constraint on the vertex degree

Is there any python package that could random generate connected graph (there is a path between every pair of vertices) on which each vertex has degree at most 4?

Thank you!

What do you mean by "fully connected"?
– 6502
2 days ago

If by "fully connected" you mean complete, then there are only five non-empty graphs with this property, all shown in this table. Do you really need a library for that?
– Andrey Tyukin
2 days ago

@ilim: actually I'm a math major and my thesis was on graph theory :-) ... the name we normally use is indeed "complete graph" and not "fully connected graph" but there's no randomness you can play with. There are theorems about k-vertex-connected graphs where you need to remove at least k vertices to disconnect the graph, or k edges if talking about edge-connectiveness but you need to specify k.
– 6502
2 days ago

I changed the word "fully connected graph" to "connected graph. I want a graph in which there is a path between every two vertices and each vertex has degree at most 4.
– yueeee
2 days ago

1 Answer
1

A simple algorithm I can think to is:

Start with one vertex

Repeat one of two random moves:

2A) Pick a random vertex with degree less than 4 and add a new vertex connected to it

2B) Pick two random vertices with degree less than 4 that are not connected and add an edge between them

until you've enough vertices/edges.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.