2. Calcul matriciel #1

Chasse au trésor !

Un problème de chemins

En partant d'une carte au trésor :

carte-au-tresor.jpg

On construit un graphe contient trois points A, B et C reliés par des chemins de la façon suivante :

graph2.png
  1. Combien y a-t-il de chemins qui permettent de passer de A à B en un tronçon ? de B à C ? de A à C ? de C à C ?

  2. Remplir le tableau suivant en indiquant le nombre de chemins d'un seul tronçon reliant les points deux à deux :

    T1=[ABCABC]T_1=\left[\begin{array}{cccc}&A&B&C\\A&\cdots&\cdots&\cdots\\B&\cdots&\cdots&\cdots\\C&\cdots&\cdots&\cdots\\\end{array}\right]

  3. La matrice d'adjacence du graphe est obtenue en ne gardant que les nombres :M1=()M_1=\left(\begin{array}{ccc}\cdots&\cdots&\cdots\\\cdots&\cdots&\cdots\\\cdots&\cdots&\cdots\\\end{array}\right)

  4. Que remarque-t-on ?

  5. Combien y a-t-il des chemins de deux tronçons qui relient A à C ? A à A ?

  6. Remplir le tableau suivant en indiquant le nombre de chemins de deux tronçons reliant les points deux à deux : T2=[ABCABC]T_2=\left[\begin{array}{cccc}&A&B&C\\A&\cdots&\cdots&\cdots\\B&\cdots&\cdots&\cdots\\C&\cdots&\cdots&\cdots\\\end{array}\right]

  7. En extrayant les nombres du tableau $T_2$ on obtient une nouvelle matrice :M2=()M_2=\left(\begin{array}{ccc}\cdots&\cdots&\cdots\\\cdots&\cdots&\cdots\\\cdots&\cdots&\cdots\\\end{array}\right)

Le nombre de chemins en deux tronçons pour joindre B à B correspond à la somme :

  • du nombre de chemins en un tronçon de B à A multiplié par le nombre de chemins en un tronçon de A à B

  • du nombre de chemins en un tronçon de B à B multiplié par le nombre de chemins en un tronçon de B à B

  • du nombre de chemins en un tronçon de B à C multiplié par le nombre de chemins en un tronçon de C à B

Soit 2×2+0×0+1×12\times2+0\times0+1\times1

  • le nombre de chemins partants de $B$ vers les autres points sont donnés par la ligne 2 (201)\left(\begin{array}{ccc}2&0&1\\\end{array}\right)

  • le nombre de chemins depuis les autres points arrivants à $B$ sont donnés par la colonne 2 (201)\left(\begin{array}{c}2\\0\\1\\\end{array}\right)

  • On définit alors la "multiplication" d'une ligne par une colonne par la formule : (201)(201)=2×2+0×0+1×1\left(\begin{array}{ccc}2&0&1\\\end{array}\right)^{\left(\begin{array}{c}2\\0\\1\\\end{array}\right)}=2\times2+0\times0+1\times1

Application :

  1. Multiplier la ligne 2 par la colonne 3

  2. Que retrouve-t-on ?

Conséquence : on peut obtenir la matrice M2M_2 des trajets à 2 tronçons à l'aide d'un calcul sur la matrice M1M_1 des trajets à 1 tronçon.

Multiplication de deux matrices

Soit A=(a1,1a1,2a1,3a2,1a2,2a2,3a3,1a3,2a3,3)A=\left(\begin{array}{ccc}a_{1,1}&a_{1,2}&a_{1,3}\\a_{2,1}&a_{2,2}&a_{2,3}\\a_{3,1}&a_{3,2}&a_{3,3}\\\end{array}\right) et B=(b1,1b1,2b1,3b2,1b2,2b2,3b3,1b3,2b3,3)B=\left(\begin{array}{ccc}b_{1,1}&b_{1,2}&b_{1,3}\\b_{2,1}&b_{2,2}&b_{2,3}\\b_{3,1}&b_{3,2}&b_{3,3}\\\end{array}\right)

On obtient alors la matrice produit

A×B=(a1,1a1,2a1,3a2,1a2,2a2,3a3,1a3,2a3,3)(b1,1b1,2b1,3b2,1b2,2b2,3b3,1b3,2b3,3)=(c1,1c1,2c1,3c2,1c2,2c2,3c3,1c3,2c3,3)A\times B=\left(\begin{array}{ccc}a_{1,1}&a_{1,2}&a_{1,3}\\a_{2,1}&a_{2,2}&a_{2,3}\\a_{3,1}&a_{3,2}&a_{3,3}\\\end{array}\right)^{\left(\begin{array}{ccc}b_{1,1}&b_{1,2}&b_{1,3}\\b_{2,1}&b_{2,2}&b_{2,3}\\b_{3,1}&b_{3,2}&b_{3,3}\\\end{array}\right)}=\left(\begin{array}{ccc}c_{1,1}&c_{1,2}&c_{1,3}\\c_{2,1}&c_{2,2}&c_{2,3}\\c_{3,1}&c_{3,2}&c_{3,3}\\\end{array}\right)

ci,j=ai,1×b1,j+ai,2×b2,j+ai,3×b3,jc_{i,j}=a_{i,1}\times b_{1,j}+a_{i,2}\times b_{2,j}+a_{i,3}\times b_{3,j}

  1. Calculer M12=M1×M1M_1^2=M_1\times M_1

  2. Que retrouve-t-on ?

  3. À l'aide de la calculatrice calculer M13M_1^3.

  4. Que nous donne cette matrice M13M_1^3. Retrouver les résultats sur le graphe.

Last updated

Was this helpful?