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

[invitec5eb4b89]

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

[invite986312212]

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.

[invite986312212]

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.

[Murzabov]

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.

[A voir en vidéo sur Futura]

[invite986312212]

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

[invitec5eb4b89]

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.

[invitec5eb4b89]

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.