Forum de Mathématiques: Maths-Forum

Soit le graphe suivant http://dedalios.free.fr/Images/ExoN1.jpeg 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_transit...

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

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

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

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

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

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), d...