Comment peut-on générer aléatoirement un graphe non orienté connexe.
C'est à dire que l'on spécifie le nombre de noeuds et notre programme génère un graphe connexe (de manière équiprobable)
Comment peut-on générer aléatoirement un graphe non orienté connexe.
C'est à dire que l'on spécifie le nombre de noeuds et notre programme génère un graphe connexe (de manière équiprobable)
Bonjour,
Je te propose une ébauche de solution qui permet de générer aléatoirement un graphe minimal (à n arêtes).
Tu commences par choisir aléatoirement 1 noeud.
Tu définis une structure de donnée "Connect" ensembliste (ou une liste) qui contient l'ensemble des noeuds déjà connectés, et une deuxième "Disconnect" des noeuds pas encore connectés.
Connect est initialisée avec l'élément choisi au hasard, Disconnect avec les autres éléments.
Tant que la Disconnect n'est pas vide :
- choisir aléatoirement 1 élément A dans Connect ;
- choisir aléatoirement 1 élément B dans Disconnect ;
- créer une arête AB dans la matrice ;
- retirer B de Disconnect et l'ajouter à Connect.
Le choix aléatoire peut consister à générer un nombre aléatoire X (les langages de programmation ont une fonctions pour ça en général), et à prendre le Xième élément de ta liste modulo le nombre d'éléments de cette liste.
Voilà, c'est mon premier post sur ce forum, j'espère ne pas avoir écrit trop de bêtises![]()
Et tous les arbres sont équiprobables...
Si on veut en plus pouvoir calculer tous les graphes, on peut le faire en ajoutant des arêtes (on peut commencer par calculer aléatoirement le nombre d'arêtes, qui devra être compris en n et n(n-1) /2), mais là, j'ai bien peur que l'équiprobabilité ne s'envole.![]()
Ok, en fait, ce n'est pas aussi évident. Contrairement à ce que l'on pourrait croire, les problèmes liant Combinatoire et Graphes ne sont pas trivials.
Mais la question demanderait une précision : Aléatoirement, oui mais selon quel loi ? Une loi uniforme ?
Si c'est le cas, ta solution algorithmique n'est pas bonne car il existe des graphes de plus de n arêtes étant connexe.
La méthode "mathématiques" intuitive pour résoudre le problème est de prendre l'ensemble des graphes de n noeuds et de k arêtes quelconques (k<= n(n-1)/2). De se restreindre au graphe connexe et d'en choisir un aléatoirement selon une loi uniforme. Mais ce n'est pas optimal... Et trouver un algorithme optimal n'est pas évident.
N'hésitait pas à poster sur cette question, je déplacerai dans le forum Algorithmique.
Non, je voulais dire qu'en partant d'un graphe connexe à n arêtes, on peut lui ajouter autant d'arêtes que nécessaires. Ainsi, on a bien généré aléatoirement un graphes connexe parmi tous ceux possibles.
Mais je suis d'accord avec Millie (c'est d'ailleurs ce que j'écrivais un peu plus tôt) : on n'a plus d'équiprobabilité. Et pour la garantir, ce n'est pas du tout simple.
Ben... oui, le but c'était de générer un graphe connexe, et la deuxième étape permet qu'il ne soit pas obligatoirement minimal.
Pour générer tous les graphes connexes, je pense qu'il faut définir un ordre sur les graphes, induit par un ordre sur les arêtes (du genre de l'ordre qu'on défini classiquement sur sur les rationnels) :
toutes les arêtes sont définies par le couple des noeud (n,m), avec n < m (on n'utilise que la moitié de la matrice) ;
(n1, m1) < (n1,m2) ssi m1 < m2 ;
(n1,m1) < (n2,m2) si n1 < n2.
Un graphe peut alors être défini par la suite de ses noeuds dans l'ordre croissant. A chaque fois que l'on ajoute un noeud, il est possible de vérifier si le graphe est connexe, et même s'il ne peut plus le devenir.
De cette manière, on pourrait éliminer les doublons. Avec l'algorithme que j'ai proposé pour en générer un, on peut générer le même graphe de plusieurs manières différentes (par exemple, on peut commencer par le noeud 1 puis ajouter le 2, ou l'inverse, ce qui fait deux manières de générer l'arête 1-2 dès la première étape).
Non, absolument pas. Construire un arbre de hauteur 1 reviendrai à choisir un sommet et à lui connecter tous les autres sommets (graphe en étoile), ce qui n'est absoluement pas ce qui est fait. Il construit simplement un arbre couvrant.
En revanche, il y a évidement toujours le problème de l'équiprobabilité :-)
Oui Alex_pi a raison. Si je n'avais pas fait ce choix aléatoire d'un noeud dans connect, l'algo n'aurait pas généré tous les graphes possibles... et il n'aurait servi à rien de gérer connect![]()
Trouver une solution à ce problème en un temps polynomial (par rapport au nombre de noeud) est apparement un problème ouvert :
http://fabien.viger.free.fr/liafa/do...generation.pdf (si j'ai bien compris... ce dont je suis pas sûr)
A vos crayons![]()
Mon algorithme est polynomial, puisque :
- atteindre le Ième un noeud parmi n (dans une liste chaînée) : en moyenne n/2 (avec une structure simple, je parcours juste la liste jusqu'au xième),
comme on choisit dans chaque liste un élément à chaque étape, on a k/2 + (n-k)/2 = n/2
- retirer un élément dans la liste : constant
- connecter : constant
nombre d'itération : n-1
Soit une complexité en n*n.
Oui tu as raison, je me suis trompé, mais mon algo fourni bien un graphe à n-1 arêtes...
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager