**TI82** TxtView file generated by CalcText - Kouri rROYFORDrp˙Enssemble ROY ET FORD---------------- Partiel 1 ---------------- Exercice 1 Determiner une matrice d'adjc M a b c d a 1 1 0 0 b 0 0 1 0 c 0 1 1 1 d 0 1 0 0 Calcul M2 M3 M4 M M M * = M2 * = M3 Matrice adjacence dessin de : (M +. M2 +. M3 +. M4) ---------------- Partiel 2 ---------------- a b c d a 0 1 1 1 b 0 1 0 1 c 0 0 0 1 d 0 0 1 1 M2 a b c d a 0 1 1 3 b 0 1 1 2 c 0 0 1 1 d 0 0 1 2 Son coef en (1,4) ? 3 Donc 3 chemin de lg2 de a vers d add abd acd Trace de M3 ? somme termes diagonales M3 a b c d a 0 1 3 5 b 0 1 2 4 c 0 0 1 2 d 0 0 1 3 TracM3 = 5 5 chemin de longeur 3 Quand est il transitif ? Quand tout les arc transitif sont établis Rajouter tout les arc pour avoir une fermeture trstv ROY WARSHALL on considčre : (a,b) (b,c) (c,d) (d,a) - ordre alpha E = entrant S = Sortant N = Nouveau E S N a (da) (ab) (db) b (ab) (bc) (ac) (db) (dc) c (ac) (cd) (ad) (bc) (bd) (dc) d (ad) (da) (ca) (bd) (db) (cb) (cd) (dc) (bc) BALMAN FORD dans chaque step dist(valeurCHF) pred(cheminLTR) V enssemble vide b a c d e s0 0 8 8 8 8 V V V V V s1 0 2 11 8 3 V ba bc V bd s2 11 2 2 6 3 bab ba bec bed bd On s'arete a step(n) n nombre de sommmet ˙ÄE