01 76 38 08 47
Logo Kartable
AccueilParcourirRechercheSe connecter

Pour profiter de 10 contenus offerts.

Logo Kartable
AccueilParcourirRechercheSe connecter

Pour profiter de 10 contenus offerts.

  1. Accueil
  2. Terminale ES
  3. Mathématiques
  4. Méthode : Déterminer et utiliser la matrice d'adjacence d'un graphe

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

Sommaire

1Ranger les sommets dans l'ordre 2Construire la matrice M vide 3Remplir la matrice M ligne par ligne 4Calculer M^n 5En déduire le nombre de chaînes de longueur n

Ce contenu a été rédigé par l'équipe éditoriale de Kartable.

Dernière modification : 07/08/2019 - Conforme au programme 2019-2020

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.

La charte éditoriale garantit la conformité des contenus aux programmes officiels de l'Éducation nationale. en savoir plus

Les cours et exercices sont rédigés par l'équipe éditoriale de Kartable, composéee de professeurs certififés et agrégés. en savoir plus

Voir aussi
  • Cours : Les graphes
  • Quiz : Les graphes
  • Méthode : Déterminer si un graphe admet une chaîne eulérienne ou un cycle eulérien
  • Exercice : Reconnaître les propriétés d'un graphe
  • Exercice : Déterminer la matrice adjacente d'un graphe
  • Exercice : Utiliser une matrice d'adjacence
  • Exercice : Déterminer la matrice de transition d'un graphe probabiliste
  • Exercice : Utiliser la matrice de transition d'un graphe probabiliste
  • Exercice : Déterminer quand il existe l'état stable d'un graphe probabiliste
  • Exercice : Dire si un graphe est connexe
  • Exercice : Déterminer si un graphe admet une chaîne eulérienne ou un cycle eulérien
  • Exercice : Trouver le plus court chemin en utilisant l'algorithme de Dijkstra

Nos conseillers pédagogiques sont à votre écoute 7j/7

Nos experts chevronnés sont joignables par téléphone et par e-mail pour répondre à toutes vos questions.
Pour comprendre nos services, trouver le bon accompagnement ou simplement souscrire à une offre, n'hésitez pas à les solliciter.

support@kartable.fr
01 76 38 08 47

Téléchargez l'application

Logo application Kartable
KartableWeb, iOS, AndroidÉducation

4,5 / 5  sur  20256  avis

0.00
app androidapp ios
  • Contact
  • Aide
  • Livres
  • Mentions légales
  • Recrutement

© Kartable 2025