Théories des graphes :D

[fatal_error]

ben tu appliques l'algo, si a la fin ta matrice M est remplie que de 1, tu dis que ton graphe est fortement connexe, sinon ben non. (je présume que ton graphe est orienté). (il faut bien prendre M avec des 1 sur la diago)

Concernant ton circuit hamiltonien, il me semble que c'est un circuit qui passe par tous les noeuds du graphe.
Il te suffit pour ca de considérer M^n (sans 1 sur la diago) (en gardant des 0 sur la diago, pour empêcher des cycles).
Et après, si tu trouves un 1 dans une case(i,j), ca signifie qu'il existe un chemin de longueur n de i à j

[dedalios]

Sur ses bases j'ai dont cette fonction pour scilab qui permet de découvrir si un graphe est ou non connexe:

A est un graphe booléen identifiant les relations entre les sommets:

( Pour créer une fonction scilab : mettre le code dans un fichier txt et modifier l'extension par .sci)

function res = EstConnexe(A)
x = size(A,1)
i=eye(x, x);
i_m = i + A
for i=1:x ;
y= bool2s(i_m^i) ;
end ;
x = size(y,1);
Z = ones(x,x);
if Z=y then res =%t ;
else;
res =%f ;
end

endfunction

exemple soit le graphe M
A B C
A 0 0 1 ou A-->C
B 1 0 1 ou B -->A + B-->C
C 1 0 0 ou C-->A

on définie M = = [ 0 0 1; 1 0 1; 1 0 0];

on installe la fonction :
on l'exécute : EstConnexe(M)
Résultat : ans = F Donc faux le graphe n'est pas connexe.

pour la fonction : Fermeturetransitive(xx)
on obtient
1. 0. 1.
1. 1. 1.
1. 0. 1.

on voit bien que la matrice n'est pas connexe.

par contre ma fonction AlgoRoyWarshall(xx)
donne :
1. 0. 1.
1. 0. 1.
1. 0. 1.
ce qui ne correspond pas à la fermeture transitive (dont peut-être une erreur sur celui-ci?)

[fatal_error]

c'est pas une erreur.
roy warshall c'est juste une optimisation pour stocker des booléens à la place de nombres.

Le 1 signifiant qu'il y a relation. Alors que dans le cas normal (par exemple la fermerture transitive), le non 0 signifie qu'il y a relation.

En l'occurrence, dans ta fermeture, tu autorises >tous< les chemins de qqconques longueur. Genre si tas un chemin de longueur 1, tu complètes avec deux boucles sur B par exemple (pour avoir ton chemin de longueur 3).

Dans l'implem de roy warshall que tu as, tu n'autorises pas la boucle B de longueur 1 par exemple (M(2,2)=0)
Si tu initialises M de la même manière donc M=M+I tu devrais obtenir le même résultat

[dedalios]

Soit le graphe suivant

on créer la matrice du graphe : M =[ 0 0 1; 1 0 1; 1 0 0];

on installe les fonctions :
exec('Algorithme de Roy Warshall.sce', -1) ;
exec('Fermeture_transitive_x .sce', -1);
exec('Fermeture_transitive .sce', -1);
exec('Fermeture_transitive .sce', -1);

on l'exécute : EstConnexe(M)
Résultat : ans = F Donc faux le graphe n'est pas connexe.

pour la fonction : Fermeturetransitive(xx)
on obtient
1. 0. 1.
1. 1. 1.
1. 0. 1.

on voit bien que la matrice n'est pas connexe.
Donc le résultat
A B C
A 1 0 1
B 1 1 1
C 1 0 1
Si l'on parcours le graphe dans la totalité
A partir de A on peut atteindre A et C.
A partir de B on peut atteindre A B et C.
A partir de C on peut atteindre A B et C.



Par contre ma fonction AlgoRoyWarshall(xx) avait une erreur l'initialisation
donne :
1. 0. 1.
1. 0. 1.
1. 0. 1.
ce qui ne correspond pas à la fermeture transitive (dont peut-être une erreur sur celui-ci?)
l'oublie de l'initalisation

function y = AlgoRoyWarshall(A)
vmax =size(A,1);
i=eye(vmax, vmax); <<--- la ligne manquante
A = i + A
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

et donc algo corrigé :
AlgoRoyWarshall(M)
ans =

1. 0. 1.
1. 1. 1.
1. 0. 1.

---- Note d'information sur les fonctions Scilab utilisée
bool2s(A) : transforme une matrice A en matrice booléenne :
ex: A =[ -4 5 1; 3 -2 1; 1 -1 0];
bool2s(A)
ans =

1. 1. 1.
1. 1. 1.
1. 1. 0

eye(vmax, vmax); création d'un matrice booléenne unité (dont tous les termes en diagonale sont égaux à 1, les autres étant nuls), de format n x n.