La question est :
Comment peut on faire cela
Est ce qu'il y'a un algorithme connu qui facilité tout ça ?
Je trouve ça un peu compliqué de générer aléatoirement un graphe
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
La question est :
Comment peut on faire cela
Est ce qu'il y'a un algorithme connu qui facilité tout ça ?
Je trouve ça un peu compliqué de générer aléatoirement un graphe
je ne suis sûr de rien il faut d'abord voir combien de graphe connexe on peut générer à partir de n noeudEnvoyé par condor_01
La question est :
Comment peut on faire cela
Est ce qu'il y'a un algorithme connu qui facilité tout ça ?
Je trouve ça un peu compliqué de générer aléatoirement un graphe
je vais me pencher là-dessus
En fait ce que je veux c'est seulement un graphe par simulation.
Je veux juste connaitre l'algorithme qui peut me générer le graphe.
Je ne vais pas générer tous les graphes connexes possibles
Le graphe complet tel que tout noeud soit relié à tout noeud me semble être un candidat plosible :-) Tu peux prendre aussi le graphe tel que chaque noeud soit relié au précédent et au suivant, ou tel que chaque noeud est relié au premier.
Après, si l'exos demande un tirage alléatoire tel que chaque graphe connexe soit équiprobablement tiré, c'est un peu plus difficile...
Ca a du arriver une ou deux fois :-)
Je rappelle que la matrice d'adjacence M est telle que pour un vecteur S de sommets, MS soit le vecteur des sommets accessibles en un coup à partir de ceux de S. Donc par exemple, (I + M + M^2)S avec I la matrice identité est l'ensemble des sommets accessibles depuis S en au plus deux coups. Je te laisse en déduire un algo qui te permettent de déterminer si un graphe non orienté est connexe, mais même si un graphe orienté l'est bien.
Dernière modification par PRomu@ld ; 14/10/2007 à 19h49. Motif: Fusion
Salut!
un graphe orienté n'est pas toujours connexe.
Ce n'est pas ce qu'il a dit, il a montré qu'avec une matrice d'adjacence, pourvu qu'on comprenait comment l'utiliser, il était trivial de montrer la connexité (ou non) d'un graphe donné, qu'il soit orienté ou non.
--
Jedaï
j'ai mal compris
Je veux un algorithme qui:
- en entrée prend le nombre de noeuds
- en sortie me donne la matrice d'adjacence d'un graphe non orienté connexe.
Ce graphe sera généré d'une manière aléatoire.
J'ai pensé à ça:
On part d'un point A de coordonnés(0,0,0)
On ajoute un autre point distance aléatoire
puis on choisit aléatoirement un point parmi ces 2 points et on le lie à un troisième point
Et ainsi de suite jusqu'à atteindre le nombre de noeuds souhaité
salut!
j'ai bien compris ce que tu veux faire
c'est justement la connexité qui pose problème
le programme pourra te construire aléatoirement un seul chemin
A-> B -> C -> D ............-> N
et te dire que c'est un graphe connexe
Après la fin du programme qui génère le graphe on peut ajouter des lignes qui ont pour but de tirer aléatoirement des noeuds non connectés (dans la matrice d'adjacence) et les connecter (ajouter des 1 dans les cases apropriées).
donc le graphe généré juste avant la fin du programme n'est pas forcément connexe
et on lui rajoute des arêtes pour qu'il le soit
Si. En gros, ce qu'il fait, c'est construire pour commencer un arbre couvrant, puis éventuellement rajouter d'autres arrêtes pour ne pas construire uniquement des arbres mais aussi des graphes avec cycles. La construction de l'arbre l'assure de la connexité.
En revanche, il est peu probable que tous les graphes soient équiprobables avec une tel méthode. Après il faut voir qu'elle est le besoin.
http://xkcd.com/221/
Oui c'est ce que je veux faire.
je ne sais pas ce que tu veux dire par équiprobable mais le plus important pour moi c'est d'avoir un graphe connexe à la fin.
Alors passons à la pratique.
Est ce que vous me conseillez un algorithme particulier ?
Bonsoir,
si avec son algorithme, il réussi à faire un arbre avant la fin, il aurait déjà assuré la connexité (comme tu l'as dit), aurait-il besoin de cycle?
tu ne veux pas nous montrer un bout de ton algorithme?
Je veux faire cet algorithme !!!!!!!!!!!!
ça, on le sait
tu as une idée maintenant tu ne veux pas commencer?
Effectivement c'est ce que je vais faire.
Je posterai mon code dès que j'avance un peu
waiting...Effectivement c'est ce que je vais faire.
Je posterai mon code dès que j'avance un peu
Equiprobable signifie que toutes les solutions ont une probabilité égale de sortir.
Pour un entier N, le nombre de graphe connexe ayant N arête est fini. Si ton programme est effectivement equiprobale, cela signifie que chaque graphe doit avoir une probabilité de 1/N d'être généré.
Répondre avec citation
Partager