Bonjour à tous,

j'aimerai pouvoir générer, à partir d'un ensemble de noeuds (spécifiés par leur coordonnée [x,y]), un graphe qui soit connexe et k-connecté.

Le paramètre k serait une entrée de mon algorithme.

Ma première idée serait d'utiliser un algorithme d'arbre recouvrant type Prime ou Kruskal afin d'avoir au moins un chemin entre chaque paire de noeud.

Ensuite, je testerais le degrés de chacun des noeuds en venant ajouter un arc entre le noeud courant et un autre noeud choisit aléatoirement pour atteindre le degré k...

Existe-t-il des algorithmes précis pour ce genre de problème?

Merci d'avance.