Comment peut-on générer uniformément un graphe aléatoire tel que les degrés sont dans un ensemble D inclus dans N, N ensemble des entiers naturels
Comment peut-on générer uniformément un graphe aléatoire tel que les degrés sont dans un ensemble D inclus dans N, N ensemble des entiers naturels
De façon naïve, je verrai le graphe comme une matrice carrée de dimension k, où k = le nombre de sommets.
Pour chaque ligne, tu choisis un nombre aléatoire correspondant au degré du sommet associé à la ligne, et tu "coches" aléatoirement les cases de la ligne pour relier ce sommet à d'autres sommets.
A noter qu'il te faut reporter par symétrie par rapport à la diagonale les cases cochées, car le graphe est non orienté, je présume. Et par conséquent, lors de l'étape précédente, il te faut tenir compte des cases déjà cochées sur la ligne.
Et le tour et joué.
Il y a un risque avec la méthode proposée.
Je traite le sommet 1, et je le lie avec différents sommets, aléatoirement.
Idem le sommet 2, etc.
Eventuellement, le sommet 1 aura été lié au sommet 100 ; idem, le sommet 2 aura été lié au sommet 100. etc etc.
Et quand j'arrive au sommet 100, il est déjà lié à 30 ou 40 sommets, ou 99 sommets au pire, alors que le sommet 100 est sensé être lié à 20 sommets.
Si effectivement la question initiale est celle-ci, alors on doit pouvoir trouver des solutions pour corriger cela. Mais il faudrait éclaircir la question.
Graphe orienté ou non ?
Tout le problème d'une ébauche d'algo non testé.
Oui, lorsqu'on coche, il faut vérifier le nombre de cases déjà cochées sur la colonne.
En remarque, cette méthode naïve ne garantit pas la connexité du graphe ainsi généré. Si cette contrainte fait également partie de l'exercice, c'est autrement plus "touchy".
Pour ajouter un grain de théorie, le besoin ressemble à l'algorithme de génération de Watts et Strogatz (https://en.wikipedia.org/wiki/Watts_and_Strogatz_model). La différence est que ce dernier garantit un degré moyen. (Exemple d'implémentation : https://github.com/JuliaGraphs/Light...graphs.jl#L105.) Il y a peut-être moyen de jouer avec le paramètre de distribution et de retravailler légèrement les graphes pour atteindre la contrainte de degré ?
Bonjour,
Pourquoi ne pas envisager un remplissage binaire et pseudo-aléatoire de la matrice d'adjacence ?
Cela doit aller assez vite, puisque la matrice est symétrique (aij = aji) et ses termes diagonaux nuls (aii = 0) en l'absence de boucle.
C'est pour l'essentiel ce que propose yahiko.
Le codage des limitations imposée ne doit pas constituer d'obstacle insurmontable:
# si l'on veut ne laisser subsister aucun sommet isolé, il suffit d'un remplissage préalable logeant au moins un point dans chaque ligne ou chaque colonne;
# si l'on désire s'assurer du caractère hamiltonien du graphe, énoncer d'abord une permutation pseudo-aléatoire des (Ns) sommets qui définira le parcours exigé - c'est une version trop contraignante d'un graphe connexe;
# le graphe deviendra cyclique dès que l'on joindra par une arête les points extrêmes de la chaîne précédente;
# la simple connexité peut résulter de l'énumération d'une série de chaînes, avec critère d'arrêt approprié sur deux indices.
Poursuivre ensuite l'ensemencement aléatoire de la matrice, en veillant à ce que le degré de tout sommet ne dépasse pas la limite convenue, et jusqu'à ce que le nombre total d'arêtes souhaité(Na) soit atteint.
Merci pour vos réponses. Je compte me servir de la liste d'adjacence pour résoudre le problème mais ca se complique. Si on limite les degrés à \Delta, je trouve la solution. Le problème est que D peut être du genre {3,5,8,..}. Prendre une séquence de degré et tester la faisabilité n'est pas une bonne si on essai avec. Je ne sais pas comment appliquer les modèles de Watts et... Pour un nombre de sommets fixé, il faut kn/2 arêtes, si kn est pair ca existe, sinon, si le nombre d'arêtes est supérieur ou inférieur, c'est impossible...
Tu n'as rien dit de la taille de ton graphe: combien comporte-t-il de sommets ? Sa matrice d'adjacence peut-elle raisonnablement faire l'objet de manipulations telles que les échanges de valeurs entre ses éléments ?
La somme des degrés est nécessairement paire, mais cette restriction n'est pas un obstacle, parce que les données de base du graphe sont les nombres (NS, NA) de sommets et d'arêtes.
As-tu songé à travailler sur une liste des degrés toujours ordonnée, par exemple dans le sens croissant, et à envisager la création progressive de nouvelles arêtes ? Et par ailleurs la substitution d'une arête par une autre, avec (ou sans) sommet commun ?
Tu pourrais ainsi te rapprocher progressivement de la liste des degrés imposée, en partant d'un graphe aléatoire connexe comportant le plus petit nombre d'arêtes (NA° = NS - 1), et le nombre imposé (N1) de sommets de degré (1).
Une piste: on a pour tout graphe connexe acyclique: N1 = 2 + N3 + 2*N4 + 3*N5 + ... + (Dm - 1)*NDm
et si sont présents (Nc) cycles: NA = NS - 1 + Nc
On trouve des liens intéressants sur la construction des graphes aléatoires (parcours très rapide):
Génération de graphes connexes aléatoires avec séquence de degrés donnée
http://fabien.viger.free.fr/liafa/docs/report-liafa.pdf
Graphes aléatoires
http://perso.ens-lyon.fr/eric.thierr...ent-picard.pdf
et aussi des algorithmes sur celui fournit par dourouc05 - là, cela n'a rien d'évident ...
La suppression d'un sommet de degré (2) suivie de la concaténation des fragments restants supprime une arête, mais conserve les degrés des autres sommets, d'où la possibilité de travailler sur un graphe réduit en procédant de la manière suivante:
1°) Classer selon l'ordre croissant la liste des degrés des (NS) sommets initiaux; le nombre d'arêtes vérifie à ce stade:
2*NA = N1 + 2*N2 + 3*N3 + ... + Dmax*NDmax .
Le contenu de la liste correspondra à la somme des éléments des (NS) colonnes de la matrice d'adjacence, dans son état final.
2°) Éliminer tous les sommets et chaînes de degré (2) en établissant un lien direct entre les centres subsistants, ce qui revient à supprimer provisoirement de la matrice les lignes et colonnes de rang (r) compris entre (N1 + 1) et (N1 + N2) - bornes incluses.
Le nombre d'arêtes vérifie désormais: 2*N'A = N1 + 3*N3 + ... + Dmax*NDmax ,
ce qui implique: NA - N'A = N2 en confirmation du constat initial, et N'S = NS - N2 pour le graphe réduit obtenu (G').
3°) Passer au graphe complet correspondant (G") en reliant entre eux tous les sommets présents; la nouvelle liste des degrés associée à l'objet devient une séquence de (N'S) termes identiques, égaux à ((N'S - 1) puisque sont exclues les liaisons multiples.
4°) Supprimer progressivement les arêtes:
a) en commençant par les sommets de rang de plus élevé;
b) en envisageant systématiquement les sommets associés de rang moindre, et d'une manière aléatoire;
c) en veillant à ce que les nouvelles valeurs des degrés ne soient jamais inférieures à celle de la liste initiale, pour les deux rangs considérés;
d) en poursuivant l'opération jusqu'à la disparition de tout écart entre les deux liste.
Le nombre d'arêtes supprimées est N'S*(N'S - 1)/2 - N'A .
5°) Insérer aléatoirement les (N2) sommets initialement exclus du réseau: les degrés des sommets actuellement présents demeurent inchangés.
La connexité du graphe final n'est pas assurée. Un marquage approprié des arêtes (à l'aide de valeurs décimales(1)) pourrait remédier à cela.
(1)) ... ou d'une paire d'indices, ou par bivaluation des arêtes créées)
Deux possibilités se présentent si l'on veut toujours parvenir à un graphe connexe, et qui partent de la liste des degrés ordonnée dans le sens croissant, et dépourvue de valeurs nulles du fait de l'exclusion des sommet isolés.
Cette liste, de longueur (NS), commence donc par (N1) termes égaux à l'unité.
1°) Réalisation d'un graphe connexe acyclique comportant (NA° = NS -1) arêtes et (N1) bouts de chaîne, par les étapes suivantes:
a) tirage aléatoire des longueurs des (N1 - 1) sous-chaînes destinées à se raccorder par la suite, sous les conditions suivantes:
# 3 <= L1 (la première présentant deux extrémités de degré égal à 1);
# 1 <= Li pour tout indice du domaine [2 ; N1 - 1] (il n'y a plus qu'une extrémité de degré 1);
# L1 + L2 + ... + LN1 - 1 = NS
b) raccordement successif des tronçons en tout sommet du graphe courant, à l'exception des extrémités, ce qui conserve le nombre (N1) de sommets de degré (1); il faudra cependant vérifier qu'aucun terme de la liste croissante des degrés ne dépasse celui de même rang de la liste initiale.
2°) À partir de ce graphe initial (G°), dont on est assuré qu'il est acyclique et connexe, et auquel il manque en principe (NA - NA°) arêtes, deux options sont envisageables:
a) créer des liens supplémentaires (donc à chaque fois des cycles) selon une procédure apparentée à celle décrite au précédent message;
b) passer au graphe complet, puis comme auparavant supprimer des liens - mais avec désormais l'obligation de préserver les arêtes du graphe connexe initial (G°); d'où l'attribution de 2 valeurs différentes aux éléments non-nuls de la matrice d'adjacence; par exemple:
# aij = 7 pour les liens du graphe connexe, à préserver impérativement,
# aij = 9 pour les autres, susceptibles de disparaître ensuite.
Cette complication aura l'intérêt de permettre une meilleure représentation visuelle du graphe, en conservant des informations sur sa structure interne.
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