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)
On donne le graphe $G$ à 5 sommets ci-dessous.
- Donner la matrice de ce graphe (en ordonnant les sommets dans l'ordre alphabétique).
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.
Il y a 5 sommets donc la matrice est une matrice carrée d'ordre 5
Les coefficients de la première ligne correspondent aux arêtes partant du sommet A
On peut contrôler les résultats en vérifiant que la somme des coefficients de chaque ligne est égale au degré du sommet correspondant à cette ligne.
La matrice obtenue est une matrice carrée symétrique dont les termes de la diagonale sont nuls. - Avec la calculatrice, calculer $M^3$.
En déduire le nombre de chaînes de longueur 3 allant du sommet B au sommet E.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^3$ (OPTN puis MAT puis MAT A$^3$)Avec la calculatrice, saisir les coefficients de $M$ puis calculer $M^3$ (OPTN puis MAT puis MAT A$^3$)
$M^3=\begin{pmatrix} 0&4&2&1&1\\ 4&4&6&6&6\\ 2&6&4&5&5\\ 1&6&5&2&2\\ 1&6&5&2&2 \end{pmatrix}$
Le nombre de chaînes de longueur 3 reliant B à E est le coefficient de 3ième ligne et de la 5ième colonne de $M^3$
Ces six chaînes sont B-A-B-E; B-C-B-E; B-D-B-E; B-E-C-E; B-D-C-E; B-A-B-C-E
Attention les fonctions ci-dessus sont désactivées en mode "visiteur", créez un compte MATHS-LYCEE.FR (gratuit)