TUTO : Graphe Simple / Niveaux
Aujourd'hui, nous allons apprendre à faire des matrices.
Nous allons donc commencer par remplir le tableau des prédécesseurs, pour cela nous allons nous aider de la matrice M. (On peut aussi s'aider d'un graph s'il y en a un...).
Dans la matrice on peut voir que la première ligne est "0 1 1 1". La première ligne correspond au "départ" de la première lettre (ici, A) la seconde ligne représente B, la troisième C etc... ensuite, les colonnes représentent les lettres d'arrivée : La première colonne représente "A" la seconde "B"... en lisant la première ligne, on peut lire ceci :
0 1 1 1 : A ne va pas vers A ; A va vers B ; A va vers C ; A va vers D.
En utilisant cette méthode de lecture de la matrice, nous allons remplir le tableau des prédécesseurs. Par exemple, on sait que A est le prédécesseur de B,C et D.
Dans la matrice on peut voir que la première ligne est "0 1 1 1". La première ligne correspond au "départ" de la première lettre (ici, A) la seconde ligne représente B, la troisième C etc... ensuite, les colonnes représentent les lettres d'arrivée : La première colonne représente "A" la seconde "B"... en lisant la première ligne, on peut lire ceci :
0 1 1 1 : A ne va pas vers A ; A va vers B ; A va vers C ; A va vers D.
En utilisant cette méthode de lecture de la matrice, nous allons remplir le tableau des prédécesseurs. Par exemple, on sait que A est le prédécesseur de B,C et D.
| Sommets | Prédécesseurs |
| A | Ø |
| B | A;C |
| C | A |
| D | A;B;C |
On nous demande ensuite de déterminer les niveaux de chaque sommet. Pour cela, nous devons d'abord répertorier les sommets ainsi que leurs successeurs.
| Sommets | Prédécesseurs | Niveau 0 | Niveau 1 | Niveau 2 | Niveau 3 |
| A | Ø | A | - - - | - - - | - - - |
| B | A;C | - - - | - - - | - - - | - - - |
| C | A | - - - | - - - | - - - | - - - |
| D | A;B;C | - - - | - - - | - - - | - - - |
On a placé le point qui n'a pas de prédécesseur au niveau 0. Maintenant nous allons supprimer tous les "A" de la colonne des prédécesseurs (puisque le A a été placé dans un niveau, ici le 0). On supprime donc les "A" et on regarde quelle(s) lettre(s) se retrouve(nt) maintenant sans prédécesseur.
| Sommets | Prédécesseurs | Niveau 0 | Niveau 1 | Niveau 2 | Niveau 3 |
| A | Ø | A | - - - | - - - | - - - |
| B | C | - - - | - - - | - - - | - - - |
| C | - - - | - - - | C | - - - | - - - |
| D | B;C | - - - | - - - | - - - | - - - |
Nous avons donc retiré tous les "A", on a pu voir que la lettre "C" se retrouve maintenant sans prédécesseur, on le place donc dans le niveau 1 et on supprime les "C" de la colonne des prédécesseurs.
| Sommets | Prédécesseurs | Niveau 0 | Niveau 1 | Niveau 2 | Niveau 3 |
| A | Ø | A | - - - | - - - | - - - |
| B | - - - | - - - | - - - | B | - - - |
| C | - - - | - - - | C | - - - | - - - |
| D | B | - - - | - - - | - - - | - - - |
Le "B" se retrouve donc sans prédécesseur et se situe maintenant dans le niveau 2. On va donc supprimer tous les B de la colonne des prédécesseurs.
| Sommets | Prédécesseurs | Niveau 0 | Niveau 1 | Niveau 2 | Niveau 3 |
| A | Ø | A | - - - | - - - | - - - |
| B | - - - | - - - | - - - | B | - - - |
| C | - - - | - - - | C | - - - | - - - |
| D | - - - | - - - | - - - | - - - | D |
Et voilà, la colonne des prédécesseurs est maintenant vide, nous avons bien complété notre tableau de niveaux.
- A : Niveau 0
- C : Niveau 1
- B : Niveau 2
- D : Niveau 3
Voici le Graphe qui correspond à notre matrice.
Pour savoir si la matrice a un chemin de longueur 4, il suffit de calculer : M^4. Pour savoir s'il y a des chemins de longueur 3 : M^3. Longueur 2 : M^2... etc.
Ici, M^4 = 0 Il n'y a aucun chemin de longueur 4 dans ce graphe.
Si on fait M^3, on peut voir qu'un chemin de longueur 3 existe : Ce chemin est : A ; C ; B ; D