Niveau école ingénieur

question sur la manipulation des graphes avec scilab

Posté par
mahaghribi 23-10-09 à 12:03

Bonjour,

Je suis entrain de travailler sur les graphes. C'est la première fois que je les manipule avec scilab. Mon problème est le suivant: J'ai construit un graphe à partir d'une matrice d'adjacence et je veux vérifier deux points:
- Est ce que mon graphe et connexe?? (le graphe n'est pas orienté!);
- Si non, comment je peux détecter les sous graphes isolés;

Merci!!

Posté par re : question sur la manipulation des graphes avec scilab 23-10-09 à 16:05

Salut.
Il y a une manière très simple de savoir si ton graphe est connexe (ce n'est pas la plus efficace au niveau de la complexité algorithmique bien sur).

Calcule $I+A+A^2+\cdots A^{n-1}$
où A est la matrice d'ajdacence et n le nombre de sommets du graphe. Si ton graphe est connexe tous les coefficients seront >0 et sinon tu verras apparaître les composantes.

Je te laisse prouver ce que je dis, c'est pas très difficile.

Posté par re : question sur la manipulation des graphes avec scilab 23-10-09 à 16:06

Bien entendu le plus efficace serait de faire un parcours de ton graphe, en profondeur par exemple, mais là il faudrait faire un peu de programmation.

Posté par re : question sur la manipulation des graphes avec scilab 23-10-09 à 16:16

Merci pour votre réponse!!!

Il faut dire que mon n=1920, cela va prendre beaucoup de temps pour chercher si mon graphe est connexe ou pas!!

Je me demandais plustôt, si on pourrait manipuler la matrice d'adjacence de façon à ce qu'on retrouve une matrice par blocs ou chaque bloc représente un sous graphe. Juste pour précision, je travaille sur le clustering des graphes et donc mon but est chercher les sous graphes qui pourraient être considérés comme des clusters.

Merci!!

Posté par re : question sur la manipulation des graphes avec scilab 23-10-09 à 17:22

Alors il faut que tu programmes un petit parcours, c'est pas trop violent.

http://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur

Il s'agit en gros de partir d'un sommet et d'explorer tant qu'on peut les nouveaux voisins.

(désolé j'arrive pas à mettre un lien correctement)

Posté par re : question sur la manipulation des graphes avec scilab 23-10-09 à 17:24

Posté par re : question sur la manipulation des graphes avec scilab 30-10-09 à 10:18

Merci beaucoup, ça m'a bien aidé!!!

Posté par re : question sur la manipulation des graphes avec scilab 04-11-09 à 12:00

Bonjour,

J'ai du programmé la fonction récursive pour chercher les sous graphes connexes d'un graphe. Mais aujourd'hui j'ai découvert toute une bibliothèque sous scilab qui permet de traiter les graphes (construction, tests..)
par exemple, pour construire un graphe on utilise la fonction "make_graph", pour tester la connexité du graphe on utilise "is_connex" et pour détecter les sous graphes (ensembles des nœuds connexes il y a la fonction "connex". L'avantage de cette fonction qu'elle est très efficace pour le clustering des graphes parce qu'elle affecte les nœuds aux sous graphes (clusters).

voila c'était la solution de mon problème, mais encore merci pour votre aide