Géneration aléatoire de graphe non orienté connexe

**condor_01** · 14/10/2007, 15h50

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)

**fremen167** · 22/10/2007, 22h17

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

**acacia** · 22/10/2007, 23h34

Envoyé par fremen167

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

Bonsoir,
le programme va construire un arbre de hauteur 1 et ça marche dans tout les cas (enfin, je pense

)

**fremen167** · 22/10/2007, 23h47

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.

**millie** · 22/10/2007, 23h53

Envoyé par fremen167

Bonsoir et merci de ce message de bienvenue,

...j'essayais d'apporter une réponse à la question du post 16 (Comment peut on générer aléatoirement un graphe non orienté connexe ?)

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.

**acacia** · 22/10/2007, 23h55

Envoyé par fremen167

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.

calculer tous les graphes, est-ce appliquer l'algorithme proposé sur tout les noeud donnés?

**fremen167** · 23/10/2007, 00h10

Envoyé par acacia

calculer tous les graphes, est-ce appliquer l'algorithme proposé sur tout les noeud donnés?

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.

**acacia** · 23/10/2007, 00h27

Envoyé par fremen167

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.

oui, mais si on rajoute des arrêtes n'importes ou sur le premier graphe connexe généré avec l'algorithme, le graphe ne perd pas sa connexité

**fremen167** · 23/10/2007, 09h46

Envoyé par acacia

oui, mais si on rajoute des arrêtes n'importes ou sur le premier graphe connexe généré avec l'algorithme, le graphe ne perd pas sa connexité

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).

alex_pi · 23/10/2007, 14h03

Envoyé par acacia

Bonsoir,
le programme va construire un arbre de hauteur 1 et ça marche dans tout les cas (enfin, je pense

)

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é :-)

**acacia** · 23/10/2007, 14h24

Envoyé par alex_pi

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é :-)

c'est ce que j'ai compris de l'algorithme (un graphe en étoile) puisque initialement aucun noeud n'est connecté à un autre, donc si on choisit un noeud aléatoirement et on le connecte à tout les autres noeud, ça fera un graphe en étoile

alex_pi · 23/10/2007, 15h53

Envoyé par acacia

c'est ce que j'ai compris de l'algorithme (un graphe en étoile) puisque initialement aucun noeud n'est connecté à un autre, donc si on choisit un noeud aléatoirement et on le connecte à tout les autres noeud, ça fera un graphe en étoile

Non puisqu'à chaque étape il choisi un élément dans connect et un dans disconnecte, et qu'il les connecte, l'élément dans connect varie d'une étape à l'autre

**fremen167** · 23/10/2007, 20h35

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

**acacia** · 23/10/2007, 21h48

Envoyé par alex_pi

Non puisqu'à chaque étape il choisi un élément dans connect et un dans disconnecte, et qu'il les connecte, l'élément dans connect varie d'une étape à l'autre

Envoyé par fremen167

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

Effectivement, je viens de dérouler ça à la main et je vois bien ce que vous venez de m'expliquer merci

**millie** · 23/10/2007, 22h34

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

**acacia** · 23/10/2007, 23h21

Envoyé par millie

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

millie, c'est de plus en plus dur

**fremen167** · 24/10/2007, 00h34

Envoyé par millie

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.

**sidahmed** · 24/10/2007, 00h39

Bonjour,

Envoyé par fremen167

Bonjour,

Je te propose une ébauche de solution qui permet de générer aléatoirement un graphe minimal (à n arêtes).

Je ne suis pas d'accord ! Un graphe connexe à n nœuds contient au moins n - 1 arêtes

Cordialement,
Sidahmed.

**fremen167** · 24/10/2007, 00h43

Oui tu as raison, je me suis trompé, mais mon algo fourni bien un graphe à n-1 arêtes...

**millie** · 24/10/2007, 09h08

Envoyé par fremen167

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.

Je parle de la génération aléatoire d'un graphe connexe selon une distribution uniforme.