Répondre à la discussion
Affichage des résultats 1 à 7 sur 7

Critère numérique de connexité d'un graphe



  1. #1
    HigginsVincent

    Critère numérique de connexité d'un graphe


    ------

    Bonjour à tous !

    J'ai un petit problème d'algo sur lequel je n'ai pas trop le temps de faire de recherches approfondies, alors je m'en remets à vous !

    Je génère aléatoirement un graphe non-orienté, et je voudrais savoir s'il est connexe (ie, si j'ai bien compris, s'il existe un chemin entre tout couple de sommets). Comment faire sans y passer des jours et des jours pour un graphe qui ne contient pas plus d'une centaine de sommets, sachant que je ne voudrais pas non plus avoir trop d'arêtes dans mon graphe ?

    Merci pour votre attention,
    V.

    -----

  2. Publicité
  3. 📣 Nouveau projet éditorial de Futura
    🔥🧠 Le Mag Futura est lancé, découvrez notre 1er magazine papier

    Une belle revue de plus de 200 pages et 4 dossiers scientifiques pour tout comprendre à la science qui fera le futur. Nous avons besoin de vous 🙏 pour nous aider à le lancer...

    👉 Je découvre le projet

    Quatre questions à explorer en 2022 :
    → Quels mystères nous cache encore la Lune 🌙 ?
    → Pourra-t-on bientôt tout guérir grâce aux gènes 👩‍⚕️?
    → Comment nourrir le monde sans le détruire 🌍 ?
    → L’intelligence artificielle peut-elle devenir vraiment intelligente 🤖 ?
  4. #2
    invite986312212
    Invité

    Re : Critère numérique de connexité d'un graphe

    moi je ferais bêtement: tu pars d'un sommet quelconque, tu marques tous les sommets adjacents à ce sommet de départ, puis tous les sommets adjacents aux précédents, etc. l'algorithme s'arrête quand une passe ne permet pas de marquer de nouveaux sommets. Avec 100 sommets ça devrait aller assez vite.

  5. #3
    invite986312212
    Invité

    Re : Critère numérique de connexité d'un graphe

    maintenant, si tu veux engendrer un graphe aléatoire connexe sur N sommets, peut-être que le plus simple est de partir d'un arbre aléatoire: on part d'un sommet quelconque (la racine de l'arbre) et on tire au hasard un sommet qui lui sera relié. ensuite, quand on a déjà un arbre à k sommets, on tire au hasard l'un des k sommets, puis l'un des (N-k) non encore inclus et on ajoute l'arête entre ces deux sommets. Quand c'est fini tu as un arbre, et tu peux toujours ajouter des arêtes au hasard. Inversement un graphe aléatoire contient toujours un graphe partiel qui est un arbre.

  6. #4
    Murzabov

    Re : Critère numérique de connexité d'un graphe

    Autre solution pas trop rafinee :

    Tu considerse une matrice NxN (N nombre de points du graphe) dont l'element aij vaut 1 si il y a une arrete entre i et j et 0 sinon. on posera aii=1 c'est a dire que je chaque sommet est relie a lui meme par une arrete)

    Le produit de cette matrice par elle meme te permet de savoir quels sont les somets relies par au moins un chemin de au plus 2 arretes de long

    La puissante p eme de cette matrice te permet de savoir quels sont les sommets relies par au moins un chemin de au plus p arretes de long

    la puissance N-1 eme de cette matrice te permet donc de connaitre la fermeture transitive de ton graphe : Si cette fermeture transitive ne contient qu'une clique (ie pas de zero dans la matrice) tom graphe et connexe. Sinon cette matrice te permet de connaitre les composantes connexes de ce graphe.

    Cette methode est tres facile a implementer avec une bibliotheque de calcul matriciel de base mais elle ne permet pas facilement la construction d'un graphe connexe. Pour construire un tel graphe la methode d'Ambrosio est a recommander.
    Dernière modification par Murzabov ; 11/01/2008 à 11h51.

  7. A voir en vidéo sur Futura
  8. #5
    invite986312212
    Invité

    Re : Critère numérique de connexité d'un graphe

    pas mal! c'est élégant. Est-ce efficace? je suppose que si on diagonalise pour calculer les puissances plus vite on va avoir des problèmes d'arrondi (?)

    autrement plus haut ma souris a fourché, il fallait lire: un graphe connexe (et pas aléatoire) contient un graphe partiel qui est un arbre

  9. #6
    HigginsVincent

    Re : Critère numérique de connexité d'un graphe

    Merci pour vos réponses !

    En fait je construis mon graphe avec comme contrainte principale la distribution des degrés de connectivité des sommets. Je commence donc par définir mes sommets, puis je parcours le graphe en reliant les sommets avec une certaine loi de probabilité. Enfin je m'arrête dès que mon graphe est connexe, et hop, il parait que cela suffit pour avoir un beau graphe avec la distribution pour les degrés de connectivité que je souhaite ! Du coup, et comme je travaille avec un logiciel qui permet facilement de faire des opérations matricielles, la proposition de Murzabov me séduit pas mal !!

    Ceci dit cet algo me parait un peu louche. Aussi je vais peut être plus m'inspirer de celui de Doar et Leslie qui fait apparaitre la distribution des degrés de connectivités dans la probabilité de relier deux noeuds et dont le critère d'arrêt est justement l'adéquation avec cette distribution.

    Si vous avez d'autres bonnes idées comme ça, n'hésitez pas !
    V.

  10. Publicité
  11. #7
    HigginsVincent

    Re : Critère numérique de connexité d'un graphe

    Pour les adeptes du logiciel R, qui veulent à la fois manipuler (construire, faire des opérations élémentaires entre graphes, générer des graphes aléatoires, visualiser etc.) et faire des stats, il y a le package igraph qui permet de faire des choses très intéressantes !

    Bon dimanche à tou-te-s,
    V.

Discussions similaires

  1. critère pour le choix d'un microcontrôleur
    Par annece dans le forum Électronique
    Réponses: 15
    Dernier message: 16/06/2012, 19h40
  2. Réponses: 12
    Dernier message: 28/05/2012, 17h58
  3. Construction d'un thermomètre numérique
    Par Arthurdu07 dans le forum Électronique
    Réponses: 21
    Dernier message: 27/04/2008, 08h50
  4. double connexité d'un disque troué
    Par Quinto dans le forum Mathématiques du supérieur
    Réponses: 11
    Dernier message: 29/09/2006, 21h00
  5. formalisation mathématique d'un graphe
    Par craz_rose dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 11/03/2005, 17h37