Matrice d'adjacence d'un graphe et nombre de chemins
Exercice corrigé - Maths expertes, terminale générale
Énoncé
On csondière le graphe suivant:
{.3}\rput(0,4){\bf$A$}
\pscircle[fillstyle=solid,fillcolor=white](4,4){.3}\rput(4,4){\bf$C$}
\pscircle[fillstyle=solid,fillcolor=white](0,0){.3}\rput(0,0){\bf$B$}
\pscircle[fillstyle=solid,fillcolor=white](2,-2){.3}\rput(2,-2){\bf$D$}
\pscircle[fillstyle=solid,fillcolor=white](6,5){.3}\rput(6,5){\bf$E$}
\end{pspicture}\]](/Generateur-Devoirs/Mex/markov/exG0/1.png)
{.3}\rput(0,4){\bf$A$}
\pscircle[fillstyle=solid,fillcolor=white](4,4){.3}\rput(4,4){\bf$C$}
\pscircle[fillstyle=solid,fillcolor=white](0,0){.3}\rput(0,0){\bf$B$}
\pscircle[fillstyle=solid,fillcolor=white](2,-2){.3}\rput(2,-2){\bf$D$}
\pscircle[fillstyle=solid,fillcolor=white](6,5){.3}\rput(6,5){\bf$E$}
\end{pspicture}\]](/Generateur-Devoirs/Mex/markov/exG0/1.png)
- Ce graphe est-il complet ? connexe ? (justifier)
- Donner la matrice d'adjacence de ce graphe. On cosnidère les sommets numérotés dans l'ordre alphabétique.
- Quel est le nombre de chemins de longueur 5 qui relient A à D
Correction
Correction
- Ce graphe n'est pas complet, car par exemple A et D ne sont pas reliés.
Ce graphe est connexe: il existe un chemin entre n'importe quel couple de sommets.
- La matrice d'adjacence est une matrice 5x5:
![\[M=\lp\begin{array}{ccccc}
0 & 1 & 1 & 0 & 1\\
1 & 0 & 1 & 1 & 0\\
1 & 1 & 0 & 1 & 0\\
0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 0
\enar\rp\]](/Generateur-Devoirs/Mex/markov/exG0_c/1.png)
- On calcule
{.3}26 & 40 \\
51 & 40 & 41 & 51 & 22 \\
51 & 41 & 40 & 51 & 22 \\
26 & 51 & 51 & 26 & 40 \\
40 & 22 & 22 & 40 & 8
\enar\rp\]](/Generateur-Devoirs/Mex/markov/exG0_c/2.png)
On trouve dans cette matrice qu'il y a 26 chaînes de longueur 5 qui relient A à D.
Tag:Chaines de Markov
Voir aussi:
Quelques devoirs
en maths expertes sur les graphes et chaînes de Markov: calcul du nombre de chemins d'une longueur donnée dans un graphe et promenade aléatoire dans un labyrinthe.
sur les graphes et chaînes de Markov. Evolution probabiliste et états stables. Traffic aérien entre 4 villes et équilibre de gaz entre deux réservoirs
