Théories des graphes :D

[yasahmed]

salut tt le monde j'ai un projet a réalisé en programmation a propos des théories des graphes c-a-d ..l'utilisateur donne la matrice et l'application dessine un graphe selon cette matrice ,mon problème est le suivant malgré qui est en relation avec les maths :D
comment j peux savoir si un graphe est connexe a partir d'une matrice binaire
attention le graphe est orienté (je veux juste l'algorithme ou les équations mathématiques )

[Nightmare]

Bonjour,

ça dépend fortement du lien entre la matrice et le graphe. Quel est-il?

[yasahmed]

le graphe se trace selon ma matrice par ex MATRICE[0][1]=0;MATRICE[2][1]=1;
c-a-d qu'il y a un chemin orienté entre le sommet 2 et 1 et aucun chemin entre 0 et 1

[Nightmare]

D'accord donc ta matrice est telle que le coef de (i,j)=1 si i et j sont reliés et 0 sinon.

Dans ce cas, la non-connexité se traduit par l'existence d'un sommet relié à aucun autre, donc une ligne composée uniquement de 0 (et par symétrie une colonne).

[yasahmed]

oui j suis d'accord avec toi mais c'est juste une cas particulière
on peut avoir une matrice dont une colonne/ligne il y a au moins un liaison mais non-connexe

[Nightmare]

Tu as tout à fait raison.

[Nightmare]

Je pense avoir une piste, mais la théorie des graphes remonte un peu :

à n fixé, que représente le coefficient de (i,j) dans la matrice ? (où M est notre matrice définie précédemment)?

[yasahmed]

oui t as raison j'avais déjà pensé a faire la puissance pour savoir le nombre de chemin entre deux point pour déduire s'il y a aucun chemin entre deux points ==> le graph est non-connexe mais j'ai trouvé des problèmes au niveau de programmation :p c'est pour cette raison je pense de trouvé une autre méthode :p
merci pour les réponses

[fatal_error]

tu peux également y aller à coup d'arbre.

Tu pars d'un noeud quelconque, et tu explores tous ces fils.
A chaque fois que t'as un nouveau fils tu ajoutes +1 au compteur.
et à la fin, ben tu compares si t'as le compteur qui vaut n, comme la taille de matrice.

Look parcours en profondeur (ou largeur)

[yasahmed]

Merci mes amis j vais l tester

[dedalios]

Une piste L'utilisation de scilab et l'algo de fermeture transitive: La matrice résultant te donne l'ensemble des sommets descendant d’un sommet donné s.

M est la matrice booléenne du graphe
I est la matrice booléenne unité (dont tous les termes en diagonale sont égaux à 1, les autres étant nuls), de format n x n.
Y est la matrice booléenne résultant
n = nombre de ligne ou de colonne de la matrice M

Résultat : Y = I + M + M^2 .... + M^(n-1) = (I+M)^(n-1)


function y=Fermeturetransitive_x(A)
x = size(A,1)
i=eye(x, x);
i_m = i + M
for i=1:x ;
y= bool2s(i_m^i) ;
end ;
endfunction

Résultat sur scilab : Y = =Fermeturetransitive_x(M)

[Cliffe]

Un parcours sur un graphe représenté par une matrice ... :ptdr:

Code: Tout sélectionner

[B][U]fonction[/U][/B] testConnexiter(graphe G)
    m // nombre d'arêtes
    n // nombre de sommets
    p // Pile
    compteur := 0;

[B][U]début[/U][/B]

    [B][U]Si[/U][/B] m >= n - 1 [B][U]alors[/U][/B]
    |
    |   empilerPile(0); // 0 : sommet de départ
    |
    |   [B][U]Tant que[/U][/B] pileNonVide(p) [B][U]faire[/U][/B]
    |   |
    |   |   r := depilerPile(p);
    |   |
    |   |   [B][U]Si[/U][/B] r n'est pas déjà traiter [B][U]alors[/U][/B]
    |   |   |
    |   |   |   marquer r comme traiter; ++compteur;
    |   |   |
    |   |   |   [B][U]Pour[/U][/B] tous les voisins de r [B][U]faire[/U][/B]
    |   |   |   |
    |   |   |   |   empilerPile(voisin);
    |   |   |   |
    |   |   |   [B][U]fait[/U][/B]
    |   |   |
    |   |   [B][U]fsi[/U][/B]
    |   |         
    |   [B][U]fait[/U][/B]
    |
    [B][U]fsi[/U][/B]

    [B][U]return[/U][/B] (compteur == n);
[B][U]fin[/U][/B]

[dedalios]

version de l’algorithme Roy-Warshall
procédure Roy-Warshall (A : tableau [1..n, 1..n] de booléen) ;
var i, j, k : entier ;
début
{initialisation}
pour i := 1 à n faire
pour j := 1 à n faire
A[i, j] := M[i, j] ;
finfaire
finfaire
{calcul de la matrice d’adjacence A de G}
pour k = 1 à n faire
pour i := 1 à n faire
pour j := 1 à n faire A[i, j] := A[i, j] ou (A[i, k] et A[k, j]) ;
finfaire
finfaire
finfaire
fin.

[dedalios]

Qu'est-ce qui définie le fait que le graphe soit connexe dans testConnexiter(graphe G).
ceci dit cela vos aussi pour les algo que j'ai posé Roy-Warshall , dans ce cas si j'ai bien compris : si la matrice M = A alors le graphe est connexe.

voici roy-Marshall pour scilab
function y = AlgoRoyWarshall(A)
vmax =size(A,1),
for i = 1:vmax ;
for j =1:vmax ;
for k= 1:vmax ;
A(i , j) = A(i , j) | (A(i , k) & A(k , j)) ;
end ;
end ;
end ;
y= bool2s(A);
endfunction

J'ai quelques doutes sur son bon fonctionnement:
A noter scilab est "Le logiciel open source gratuit de calcul numérique" disponible sur le site http://www.scilab.org/

[fatal_error]

Qu'est-ce qui définie le fait que le graphe soit connexe dans testConnexiter(graphe G).

si le graphe est connexe, alors tous les noeuds doivent etre relies.

Si tu pars d'un noeud et que tu explores tous les voisins de proche en proche, et qu'au final tu as exploré m noeuds différent alors que le graphe en possède n, ca veut dire que tu as des noeuds isolés et que le graphe est pas connexe.

ceci dit cela vos aussi pour les algo que j'ai posé Roy-Warshall , dans ce cas si j'ai bien compris : si la matrice M = A alors le graphe est connexe.

non c'est pas ca.
La matrice d'adjacence M te donne la relation entre deux noeuds. 1 dans la case (i,j) te dit il existe un chemin de i à j.
En l'occurrence pour tester la connexité, il faut s'assurer qu'il existe un chemin du noeud (par exemple 1) à tous les autres noeuds.

Le but d'élever M à la puissance n est de déterminer tous les chemins de longueur 1 à n. Bref la connexité est donnée par une matrice normalement remplie uniquement de 1.

[Cliffe]

Ne pas confondre graphe connexe et graphe complet ...

[fatal_error]

Ne pas confondre graphe connexe et graphe complet ...

hors de propos

[dedalios]

si le graphe est connexe, alors tous les noeuds doivent etre relies.

Si tu pars d'un noeud et que tu explores tous les voisins de proche en proche, et qu'au final tu as exploré m noeuds différent alors que le graphe en possède n, ca veut dire que tu as des noeuds isolés et que le graphe est pas connexe.


non c'est pas ca.
La matrice d'adjacence M te donne la relation entre deux noeuds. 1 dans la case (i,j) te dit il existe un chemin de i à j.
En l'occurrence pour tester la connexité, il faut s'assurer qu'il existe un chemin du noeud (par exemple 1) à tous les autres noeuds.

Le but d'élever M à la puissance n est de déterminer tous les chemins de longueur 1 à n. Bref la connexité est donnée par une matrice normalement remplie uniquement de 1.

-- Donc si j'obtient par l'algo de fermeture transitive ou Algorithme de Roy Warshall une matrice de type
( 1 1 1
1 1 1
1 1 1) mon graphe est connexe

[fatal_error]

ouais, c'est ca

[dedalios]

Donc voila sur un exercice : j'ai le schéma d'un graphe et je dois dire s'il est fortement connexe.

J'ai uniquement à ma disposition dans le cours la fermeture transitive et l'algo de Algorithme de Roy Warshall:

le corrigé de l'exercice dit ceci sans plus d'explication

le graphe suivant est-il fortement connexe? :Non
Existe-t-il des circuits hamiltoniens ? :Non

Je reste assez perplexe après moult relecture du cours qui ne parle null-part de notion circuits hamiltoniens ou de graphe connexe pour faire la relation avec la fermeture transitive, l'algo de Algorithme de Roy Warshall et la réponse donné par l'enseignant à l'exercice ci-dessus quelque peut légère.