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:

\[\psset{unit=.8cm} 
\begin{pspicture}(1,-2.3)(4.5,5.5)
\psline(4,4)(0,4)(0,0)(4,4)
\psline(0,0)(2,-2)
\psline(0,4)(6,5)
\psline(2,-2)(6,5)
\psline(4,4)(2,-2)
\pscircle[fillstyle=solid,fillcolor=white](0,4){.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}\]

  1. Ce graphe est-il complet ? connexe ? (justifier)
  2. Donner la matrice d'adjacence de ce graphe. On cosnidère les sommets numérotés dans l'ordre alphabétique.
  3. Quel est le nombre de chemins de longueur 5 qui relient A à D



Correction

Correction

  1. 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.
  2. 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\]

  3. On calcule
    \[M^5=\lp\begin{array}{ccccc}
  26 & 51 & 51 & \pscircle[fillstyle=solid,linecolor=red,fillcolor=white](.2,.12){.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\]


    On trouve dans cette matrice qu'il y a 26 chaînes de longueur 5 qui relient A à D.


Tag:Chaines de Markov

Autres sujets au hasard: Lancer de dés



Voir aussi:

Quelques devoirs


LongPage: h2: 3 - h3: 0