Les Graphs Simples

Les graphs simples : Programme de BTS

TUTO : Graphe Simple / Niveaux

Aujourd'hui, nous allons apprendre à faire des matrices.

énoncer


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.

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

Graphe

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