Déterminer et utiliser la matrice d'adjacence d'un grapheMéthode

Pour construire la matrice d'adjacence M d'un graphe, on liste sommet par sommet les arêtes qui les relient entre eux.

Une matrice d'adjacence à la puissance n permet de connaître le nombre de chemins de longueurs n entre n'importe quel couple de point du graphe.

On considère le graphe suivant :

-

Construire sa matrice d'adjacence M puis déterminer le nombre de chaînes de longueur 3 reliant les sommets A et C.

Etape 1

Ranger les sommets dans l'ordre

On range les sommets dans un ordre déterminé.

  • Si les sommets sont des lettres, on les range de préférence dans l'ordre alphabétique.
  • Si ce sont des numéros, on les range dans l'ordre croissant.

On range les sommets dans l'ordre alphabétique : A, B, C, D.

Etape 2

Construire la matrice M vide

On construit la matrice vide en associant à chaque ligne et à chaque colonne un sommet, en respectant l'ordre déterminé précédemment.

On construit la matrice vide, en notant les en-têtes des lignes et des colonnes.

M = \begin{pmatrix} & A & B & C &D \cr\cr A & & & & \cr\cr B & & & & \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}

Etape 3

Remplir la matrice M ligne par ligne

Pour chaque ligne, on complète colonne par colonne :

  • Si le sommet associé à cette ligne est relié (en étant le point de départ de l'arrête dans le cas d'un graphe orienté), au sommet associé à la colonne, on marque le chiffre 1.
  • Sinon on marque le chiffre 0.

La première ligne correspond aux arêtes partant du sommet A :

  • Il n'y a pas de boucle en A : on note donc 0 sur la première colonne.
  • Il y en a une vers B : on note donc 1 sur la deuxième colonne.
  • Il y en a une vers C : on note donc 1 sur la troisième colonne.
  • Il y en a une vers D : on note donc 1 sur la dernière colonne.

On obtient :

M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & & & & \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}

La deuxième ligne correspond aux arêtes partant du sommet B :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers D : on note donc 1 sur la dernière colonne.

On note 0 au niveau des autres colonnes.

On obtient :

M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}

La troisième ligne correspond aux arêtes partant du sommet C :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers elle-même : on note donc 1 sur la troisième colonne.

On note 0 au niveau des autres colonnes.

On obtient :

M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & 1& 0& 1& 0\cr\cr D & & & & \end{pmatrix}

La dernière ligne correspond aux arêtes partant du sommet D :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers B : on note donc 1 sur la deuxième colonne.

On note 0 au niveau des autres colonnes.

Finalement, on obtient la matrice d'adjacence M :

M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & 1& 0& 1& 0\cr\cr D & 1& 1& 0&0 \end{pmatrix}

Etape 4

Calculer M^n

Afin de trouver le nombre de chaînes possibles de longueur n reliant deux points d'un graphe, on doit préalablement calculer M^n.

Sauf mention contraire de l'énoncé, on peut effectuer le calcul de M^n à la calculatrice.

On cherche le nombre de chemins de longueur 3 entre les sommets A et C. On calcule donc au préalable M^3.

À l'aide la calculatrice, on obtient :

M^3 = \begin{pmatrix} 3 &4 & 4&4 \cr\cr 4& 2& 2& 3 \cr\cr 4& 2& 3& 2 \cr\cr 4& 3& 2& 2\end{pmatrix}

Etape 5

En déduire le nombre de chaînes de longueur n

Le nombre de chaînes de longueur n partant du sommet I et allant vers le sommet J est égal au coefficient de a_{ij} (le coefficient à l'intersection de la ligne correspondant au sommet I et de la colonne correspondant au sommet J) de la matrice M^n.

On en déduit le nombre de chemins de longueur n reliant les deux points.

Dans un graphe non orienté, le nombre de chaînes reliant I à J est égal au nombre de chemins reliant J à I, donc a_{ij}=a_{ji}.

Le nombre de chaînes de longueur 3 entre les sommets A et C est donné par le coefficient correspondant à la ligne A et à la colonne C de la matrice M^3.

M^3 = \begin{pmatrix} 3 &4 & \textcolor{Red}{4}&4 \cr\cr 4& 2& 2& 3 \cr\cr 4& 2& 3& 2 \cr\cr 4& 3& 2& 2\end{pmatrix}

Il existe donc 4 chaînes de longueur 3 reliant A à C.

Si le graphe n'est pas orienté, la matrice d'adjacence est symétrique.

La présence d'un 1 sur la diagonale de la matrice M signifie que le sommet en question est relié à lui-même.

Questions fréquentes

Quelles sont les matières disponibles sur Kartable ?

Sur Kartable, l'élève accède à toutes les matières principales de la primaire au lycée, y compris pour les spécialités et les options. Mathématiques, physique-chimie, SVT, sciences, français, littérature, histoire, géographie, enseignement moral et civique, SES, philosophie, anglais, allemand et espagnol.
Inscrivez-vous

Les cours sont-ils conformes aux programmes officiels de l'Education nationale ?

L'intégralité des cours sur Kartable est rédigée par des professeurs de l'Éducation nationale et est conforme au programme en vigueur, incluant la réforme du lycée de l'année 2019-2020.
Choisissez votre formule

L'élève peut-il accéder à tous les niveaux ?

Sur Kartable, l'élève peut accéder à toutes les matières dans tous les niveaux de son choix. Ainsi, il peut revenir sur les notions fondamentales qu'il n'aurait pas comprises les années précédentes et se perfectionner.
Plus d'info

Kartable est-il gratuit ?

L'inscription gratuite donne accès à 10 contenus (cours, exercices, fiches ou quiz). Pour débloquer l'accès illimité aux contenus, aux corrections d'exercices, mode hors-ligne et téléchargement en PDF, il faut souscrire à l'offre Kartable Premium.
Plus d'info

Qui rédige les cours de Kartable ?

L'intégralité des contenus disponibles sur Kartable est conçue par notre équipe pédagogique, composée de près de 200 enseignants de l'Éducation nationale que nous avons sélectionnés.
Afficher plus

Qu'est ce que le service Prof en ligne ?

L'option Prof en ligne est un service de chat en ligne entre élèves et professeurs. Notre Prof en ligne répond à toutes les questions sur les cours, exercices, méthodologie et aide au devoirs, pour toutes les classes et dans toutes les matières. Le service est ouvert du lundi au vendredi de 16h à 19h pour les membres ayant souscrit à l'option.
Choisissez votre formule