Publications MATHS-LYCEE.FR
Aide en ligne avec WhatsApp*, un professeur est à vos côtés à tout moment! Essayez!
Un cours particulier à la demande!
Envoyez un message WhatsApp au 07 67 45 85 81 en précisant votre nom d'utilisateur.*période d'essai ou abonnés premium(aide illimitée, accès aux PDF et suppression de la pub)
La matrice $M$ est la matrice d'un graphe dont les sommets sont numérotés de 1 à 6 dans l'ordre croissant.
$\begin{pmatrix} 0&1&1&0&1&0\\ 1&0&1&1&1&1\\ 1&1&0&0&0&1\\ 0&1&0&0&0&0\\ 1&1&0&0&0&1\\ 0&1&1&0&1&0 \end{pmatrix}$
$\begin{pmatrix} 0&1&1&0&1&0\\ 1&0&1&1&1&1\\ 1&1&0&0&0&1\\ 0&1&0&0&0&0\\ 1&1&0&0&0&1\\ 0&1&1&0&1&0 \end{pmatrix}$
- Représenter le graphe $G$ dont $M$ est la matrice.
Matrice associée à un graphe
La matrice associée à un graphe d'ordre $n$ dont les sommets sont numérotés de 1 à n est une matrice carrée de dimension $n$, où le terme à l'intersection de la iième ligne et de la jième colonne est nombre d'arêtes reliant i et j.
Cette matrice est appelée matrice d'adjacence du graphe.
Le sommet numéro 1 est adjacent aux sommets 2, 3 et 5 (coefficients de la première ligne de la matrice)Le sommet numéro 1 est adjacent aux sommets 2, 3 et 5 (coefficients de la première ligne de la matrice)...
La somme des coefficients d'une ligne de la matrice est égale au degré du sommet correspondant à cette ligne - Avec la calculatrice, calculer $M^4$.
En déduire le nombre de chaînes de longueur 4 allant du sommet 2 au sommet 4.Nombre de chemins de longueur $p$
Nombre de chaînes de longueur $p$}{Soit $G$ un graphe d'ordre $n$ et de matrice d'adjacence $M$.
Le coefficient $m_{ij}$ de la matrice $M^p$ ($p$ entier naturel non nul) est le nombre de chaînes de longueur $p$ reliant les sommets $i$ et $j$.}avec la calculatrice, saisir les coefficients de $M$ puis calculer $M^4$ (OPTN puis MAT puis MAT A$^4$)$M^4=\begin{pmatrix} 25&26&17&9&17&25\\ 26&41&26&8&26&26\\ 17&26&25&9&25&17\\ 9&8&9&5&9&9\\ 17&26&25&9&25&17\\ 25&26&17&9&17&25 \end{pmatrix}$
Le nombre de chaînes de longueur 4 allant du sommet 2 au sommet 4 est le coefficient de la deuxième ligne et de la quatrième colonne de $M^4$.
Attention les fonctions ci-dessus sont désactivées en mode "visiteur", créez un compte MATHS-LYCEE.FR (gratuit)