créer un graph aléatoire

[Donato Cereghetti]

Bonjour,

je voudrais créer un liste des graphes générés au hasard qui ayant les caractéristiques suivantes:
- il doivent être connexes
- il doivent être de moins en moins connectés.

Je appliqué un "for i in" au "erdos.renji,game": cette demarche permet de creer des graphes de moins en moins connectés; le problème c'est qu'ils ne seront pas forcemment connexes.

Est-ce que quelcun sait comment faire?

Merci d'avance

dc

[Baptiste LAPORTE]

Bonjour,
il y a déjà une erreur dans le nom de la fonction qui est en fait

Code : Tout sélectionner

erdos.renyi.game()

du package igraph.
Je pense que pour avoir des graphes connexes, il suffit que le graphe fortement connexe existe, c'est à dire que pour le graphe g, la fonction graph.cohesion(g), renvoie un nombre différent de 0.
Sinon on peut programmer soit même les parcours en largeur ou en profondeur du graphe, pour savoir si le graphe est connexe.
Inclure un if dans la boucle for marchera peut être.

Il existe toutefois d'autres algorithmes pour la recherche des plus courts chemins si c'est ce qui est recherché (algo de Kruskall, Prim, ...)