# 2. Calcul matriciel #1 {% file src="" %} ## **Un problème de chemins** En partant d'une carte au trésor : ![carte-au-tresor.jpg](https://lh3.googleusercontent.com/-3QTE11Hee94/XFf9HexfC_I/AAAAAAAACGU/-JaatuwZzOMLN86NcTBgtmzHfGafH5WOwCLcBGAs/s0/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](https://lh3.googleusercontent.com/-KieCIaIM82w/XFLJpiiC2pI/AAAAAAAACFI/kIIqRBtz6fwcNfp-gEC1AJslko6NOjdyACLcBGAs/s0/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 : $$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 :$$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 : $$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 :$$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\times2+0\times0+1\times1$$ * le nombre de chemins partants de $B$ vers les autres points sont donnés par la ligne 2 $$\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 $$\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 : $$\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 $$M\_2$$ des trajets à 2 tronçons à l'aide d'un calcul sur la matrice $$M\_1$$ des trajets à 1 tronçon. **Multiplication de deux matrices** Soit $$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=\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\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)$$ où $$c\_{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 $$M\_1^2=M\_1\times M\_1$$ 2. Que retrouve-t-on ? 3. À l'aide de la calculatrice calculer $$M\_1^3$$. 4. Que nous donne cette matrice $$M\_1^3$$. Retrouver les résultats sur le graphe.