Graphes orientés : matrice d'adjacence et nombre de chemins - Exercice 1

25 min
40
On considère le graphe orienté GG représenté ci-dessous, dont les sommets sont rangés dans l'ordre alphabétique. Sa matrice d'adjacence MM est la matrice carrée d'ordre 44 dont le coefficient de la ligne ii et de la colonne jj est égal au nombre d'arcs allant du ii-ième sommet au jj-ième sommet.
Question 1

Donner la matrice d'adjacence MM du graphe GG .

Correction
La première ligne correspond aux arcs partant du sommet AA .
Il n'y a pas d'arc qui va de AA vers AA , c'est-à-dire il n'y a pas de boucle en AA . Il y aura donc 00 sur la première ligne et première colonne.
Il y a un arc qui va de AA vers BB . Il y aura donc 11 sur la première ligne et deuxième colonne.
Il y a un arc qui va de AA vers CC . Il y aura donc 11 sur la première ligne et troisième colonne.
Il n'y a pas d'arc qui va de AA vers DD . Il y aura donc 00 sur la première ligne et quatrième colonne.
On procède de même pour les lignes suivantes, qui correspondent aux arcs partant de BB , de CC et de DD .
Finalement :
M=(0110001000011100)M=\left(\begin{array}{cccc} {0} & {1} & {1} & {0} \\ {0} & {0} & {1} & {0} \\ {0} & {0} & {0} & {1} \\ {1} & {1} & {0} & {0} \end{array}\right)

Question 2

Pourquoi la matrice MM n'est-elle pas symétrique, contrairement à la matrice d'adjacence d'un graphe non orienté ?

Correction
Il y a un arc allant de AA vers BB , mais pas d'arc allant de BB vers AA : le coefficient de la première ligne et de la deuxième colonne vaut 11 alors que celui de la deuxième ligne et de la première colonne vaut 00 .
Dans un graphe non orienté, une arête entre deux sommets se parcourt dans les deux sens, donc ces deux coefficients sont toujours égaux ; ce n'est plus le cas pour un graphe orienté.
Question 3

Que représente la somme des coefficients d'une ligne de MM ? d'une colonne de MM ? Vérifier avec le sommet DD .

Correction
Le degré sortant d’un sommet AA est le nombre d'arêtes dont le sommet AA est le point de départ.
Le degré entrant d’un sommet AA est le nombre d'arêtes dont le sommet AA est le point d'arrivée.
La ligne d'un sommet compte les arcs qui en partent :
la somme des coefficients d'une ligne est le degré sortant du sommet

La colonne d'un sommet compte les arcs qui y arrivent :
la somme des coefficients d'une colonne est le degré entrant du sommet

Pour le sommet DD : la quatrième ligne de MM est (1100)\left(\begin{array}{cccc} {1} & {1} & {0} & {0} \end{array}\right) , de somme 22 (DD est le point de départ des arcs vers AA et vers BB), et la quatrième colonne contient un seul 11 (l'arc allant de CC vers DD) : le degré entrant de DD est 11 .
Question 4

Calculer, sans calculatrice, le coefficient de la quatrième ligne et de la troisième colonne de M2M^{2} , puis interpréter le résultat.

Correction
  • Le coefficient situé à la ligne ii et à la colonne jj de A×BA\times B est la somme des produits des coefficients de la ligne ii de AA par les coefficients correspondants de la colonne jj de BB.
    • Soit GG un graphe et MM sa matrice d’adjacence.
    Le nombre de chemins de longueur nn joignant le sommet ii au sommet jj est donné par le terme d’indice i,ji,j de la matrice MnM^{n}
    Comme M2=M×MM^{2}=M\times M , ce coefficient s'obtient avec la quatrième ligne de MM , (1100)\left(\begin{array}{cccc} {1} & {1} & {0} & {0} \end{array}\right) , et la troisième colonne de MM , (1100)\left(\begin{array}{c} {1} \\ {1} \\ {0} \\ {0} \end{array}\right) :
    1×1+1×1+0×0+0×0=21\times 1+1\times 1+0\times 0+0\times 0=2
    Il y a donc 22 chemins de longueur 22 allant de DD à CC :
    D−A−CD-A-C et D−B−CD-B-C

    Question 5

    À l'aide de la calculatrice, donner M3M^{3} . Combien y a-t-il de chemins de longueur 33 allant de CC à CC ? Les citer.

    Correction
    Soit GG un graphe et MM sa matrice d’adjacence.
    Le nombre de chemins de longueur nn joignant le sommet ii au sommet jj est donné par le terme d’indice i,ji,j de la matrice MnM^{n}
    D'après la calculatrice, on obtient :
    M3=(1101110001200012)M^{3}=\left(\begin{array}{cccc} {1} & {1} & {0} & {1} \\ {1} & {1} & {0} & {0} \\ {0} & {1} & {2} & {0} \\ {0} & {0} & {1} & {2} \end{array}\right)
    Nous allons prendre la valeur de l'intersection entre la troisième ligne (en référence au sommet CC) et la troisième colonne (en référence au sommet CC)
    Nous mettons en rouge\red{\text{en rouge}} cette valeur dans la matrice M3M^{3}
    M3=(1101110001200012)M^{3}=\left(\begin{array}{cccc} {1} & {1} & {0} & {1} \\ {1} & {1} & {0} & {0} \\ {0} & {1} & {{\color{red}{2}}} & {0} \\ {0} & {0} & {1} & {2} \end{array}\right)
    Il y a donc 2{\color{red}{2}} chemins de longueur 33 allant du sommet CC au sommet CC .
    Ce sont :
    C−D−A−CC-D-A-C et C−D−B−CC-D-B-C

    Question 6

    Peut-on aller de BB à AA en suivant exactement 22 arcs ? exactement 33 arcs ?

    Correction
    D'après la calculatrice :
    M2=(0011000111000120)M^{2}=\left(\begin{array}{cccc} {0} & {0} & {1} & {1} \\ {0} & {0} & {0} & {1} \\ {1} & {1} & {0} & {0} \\ {0} & {1} & {2} & {0} \end{array}\right)
    Le coefficient de la deuxième ligne et de la première colonne de M2M^{2} est nul :
    on ne peut pas aller de BB à AA en suivant exactement 22 arcs

    D'après la question 55 , le coefficient de la deuxième ligne et de la première colonne de M3M^{3} vaut 11 :
    il existe un seul chemin de longueur 33 allant de BB à AA : B−C−D−AB-C-D-A

    Signaler une erreur

    Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

    Connecte-toi ou crée un compte pour signaler une erreur.