insight.Se connecter

Maths expertes · Terminale

Graphes et matrice d'adjacence : cours et fiche de révision (Maths expertes, Terminale)

Programme officiel, session 2027. Mis à jour le 12 novembre 2026. 9 min de lecture.

Ce que contient ce chapitre

  • Lire un graphe : sommets, arêtes, ordre, degré
  • Reconnaître le graphe complet et compter ses arêtes
  • Suivre une chaîne et tester la connexité
  • Traduire une situation en graphe
  • Écrire la matrice d'adjacence d'un graphe
  • Compter les chemins avec les puissances de M
  • Démontrer la formule des chemins

Un réseau de bus, un groupe d'amis, un tournoi : dès que tu étudies des objets et leurs liens, tu les représentes par des points reliés par des traits, c'est-à-dire par un graphe. Tu vas apprendre à le décrire, à modéliser une situation par un graphe, à le coder par une matrice et à compter ses chemins grâce aux puissances de cette matrice.

Graphe, sommets, arêtes

Un graphe est formé d'un ensemble fini de points, les sommets, et de liens entre certains d'entre eux, les arêtes. Ici, une arête relie toujours deux sommets distincts, et deux sommets sont reliés par au plus une arête. Seules comptent les paires de sommets reliées, pas la forme du dessin.

Exemple

Le graphe GG a pour sommets AA, BB, CC, DD et pour arêtes AA–BB, AA–CC, BB–CC, BB–DD, CC–DD. Il n'y a pas d'arête entre AA et DD. Ce graphe sert dans tout le cours.

Sommets adjacents, ordre, degré

  • Deux sommets sont adjacents (on dit aussi voisins) lorsqu'une arête les relie.
  • L'ordre d'un graphe est son nombre de sommets.
  • Le degré d'un sommet est le nombre d'arêtes dont il est une extrémité, c'est-à-dire le nombre de ses voisins.

Exemple résolu

Dans GG, AA et BB sont adjacents, AA et DD non. GG est d'ordre 4 (il a 4 sommets et 5 arêtes). Degrés (nombre de voisins) : AA : 2 (BB, CC) ; BB : 3 (AA, CC, DD) ; CC : 3 (AA, BB, DD) ; DD : 2 (BB, CC).

Le graphe complet

Un graphe d'ordre nn est complet lorsque deux sommets distincts quelconques sont toujours adjacents. On le note souvent KnK_n. Alors :

  • chaque sommet est adjacent aux n−1n-1 autres : tous les sommets sont de degré n−1n-1 ;
  • KnK_n possède n(n−1)2\dfrac{n(n-1)}{2} arêtes.

Pourquoi ? Chacun des nn sommets est l'extrémité de n−1n-1 arêtes, soit n(n−1)n(n-1) extrémités. Chaque arête ayant deux extrémités, ce décompte compte chaque arête deux fois : on divise par 2.

Exemple résolu

Six équipes disputent un tournoi où chacune rencontre une fois chacune des autres. Équipes et matchs sont les sommets et les arêtes d'un graphe où deux sommets quelconques sont adjacents : c'est K6K_6. Chaque équipe joue 6−1=56-1=5 matchs et le tournoi en compte 6×52=15\dfrac{6\times5}{2}=15.

GG n'est pas complet : AA et DD ne sont pas adjacents. En ajoutant l'arête AA–DD, on obtient K4K_4, qui a bien 4×32=6\dfrac{4\times3}{2}=6 arêtes.

Chaînes et connexité

Chaîne et longueur

Une chaîne est une suite de sommets dans laquelle deux sommets consécutifs sont adjacents. Sa longueur est le nombre d'arêtes parcourues, c'est-à-dire le nombre de sommets de la suite moins 1. Une chaîne peut repasser par un sommet ou une arête déjà empruntés.

Exemple résolu

Dans GG :

  • AA–BB–DD est une chaîne de longueur 2 : elle emprunte AA–BB puis BB–DD ;
  • AA–CC–BB–DD est une chaîne de longueur 3 ;
  • AA–BB–AA–CC est aussi une chaîne de longueur 3, qui repasse par AA ;
  • AA–DD–CC n'est pas une chaîne, car AA et DD ne sont pas adjacents.

Graphe connexe

Un graphe est connexe lorsque deux sommets quelconques sont toujours reliés par au moins une chaîne : il est « d'un seul tenant ». Pour le prouver, il suffit de trouver un sommet relié par une chaîne à chacun des autres ; pour prouver le contraire, exhibe deux sommets qu'aucune chaîne ne relie.

Exemple résolu

GG est connexe : BB est adjacent à AA, CC et DD, donc deux sommets quelconques sont reliés par une chaîne passant par BB. Le graphe HH de sommets S1S_1 à S5S_5 et d'arêtes S1S_1–S2S_2, S2S_2–S3S_3, S4S_4–S5S_5 n'est pas connexe : depuis S1S_1, on n'atteint que S2S_2 et S3S_3, donc aucune chaîne ne relie S1S_1 à S4S_4.

Modéliser une situation par un graphe

Pour modéliser, réponds à deux questions : quels objets deviennent les sommets ? Quelle relation se traduit par une arête ? Traduis ensuite la question posée dans le vocabulaire des graphes.

Exemple résolu

Des lignes de bus directes relient cinq villes : V1V_1 et V2V_2, V1V_1 et V3V_3, V2V_2 et V3V_3, V3V_3 et V4V_4, V4V_4 et V5V_5.

  • Sommets : les villes ; arêtes : les lignes directes. Le graphe est d'ordre 5.
  • « Combien de lignes desservent V3V_3 ? » se traduit par le degré de V3V_3 : 3.
  • « Peut-on aller de toute ville à toute autre ? » se traduit par la connexité : oui, car V3V_3 est relié à V1V_1, V2V_2, V4V_4 par une arête et à V5V_5 par V3V_3–V4V_4–V5V_5.

Graphe orienté

Quand la relation a un sens (rue à sens unique, « suit » sur un réseau social), on utilise un graphe orienté : chaque lien est un arc, d'un sommet de départ vers un sommet d'arrivée. Un chemin est une suite de sommets reliés par des arcs pris dans leur sens ; sa longueur est son nombre d'arcs.

La matrice d'adjacence

On numérote une fois pour toutes les sommets d'un graphe d'ordre pp, de 11 à pp. La matrice d'adjacence du graphe est la matrice carrée MM d'ordre pp dont le coefficient mijm_{ij}, ligne ii et colonne jj, vaut 11 si les sommets ii et jj sont adjacents (graphe orienté : s'il existe un arc de ii vers jj), et 00 sinon.

Pour un graphe non orienté :

  • MM est symétrique (mij=mjim_{ij}=m_{ji}) : une arête relie ii à jj comme jj à ii ;
  • sa diagonale ne contient que des 00, aucune arête ne reliant un sommet à lui-même ;
  • la somme des coefficients de la ligne ii est le degré du sommet ii.

Exemple résolu

Pour GG, dans l'ordre AA, BB, CC, DD, la ligne de AA porte un 11 dans les colonnes de BB et de CC, un 00 ailleurs ; on fait de même pour chaque sommet :

M=(0110101111010110)M=\begin{pmatrix}0&1&1&0\\1&0&1&1\\1&1&0&1\\0&1&1&0\end{pmatrix}

Contrôle : MM est symétrique et les sommes des lignes, 22, 33, 33, 22, redonnent les degrés.

Exemple orienté. Sur un réseau social, PP suit QQ et RR, QQ suit RR, RR suit PP ; un arc va de XX vers YY si XX suit YY. Dans l'ordre PP, QQ, RR :

N=(011001100)N=\begin{pmatrix}0&1&1\\0&0&1\\1&0&0\end{pmatrix}

NN n'est pas symétrique : PP suit QQ, mais QQ ne suit pas PP.

Compter les chemins avec les puissances de la matrice

Théorème. Soit MM la matrice d'adjacence d'un graphe d'ordre pp, orienté ou non. Pour tout entier n⩾1n\geqslant1, le coefficient de MnM^n situé ligne ii, colonne jj, est égal au nombre de chaînes (de chemins si le graphe est orienté) de longueur nn allant du sommet ii au sommet jj.

En particulier, il existe une chaîne de longueur nn de ii à jj si et seulement si ce coefficient n'est pas nul.

Exemple résolu

Pour GG, on calcule M2=M×MM^2=M\times M ligne par colonne. Ligne AA, colonne DD : la ligne de AA est 00, 11, 11, 00, la colonne de DD aussi, d'où 0×0+1×1+1×1+0×0=20\times0+1\times1+1\times1+0\times0=2. On procède ainsi pour chaque coefficient, puis M3=M2×MM^3=M^2\times M :

M2=(2112132112312112)M3=(2552545555452552)\begin{gathered}M^2=\begin{pmatrix}2&1&1&2\\1&3&2&1\\1&2&3&1\\2&1&1&2\end{pmatrix} \\ M^3=\begin{pmatrix}2&5&5&2\\5&4&5&5\\5&5&4&5\\2&5&5&2\end{pmatrix}\end{gathered}
  • Ligne AA, colonne DD de M2M^2 : 22, les chaînes AA–BB–DD et AA–CC–DD.
  • Ligne AA, colonne BB de M3M^3 : 55, les chaînes AA–BB–AA–BB, AA–BB–CC–BB, AA–BB–DD–BB, AA–CC–AA–BB et AA–CC–DD–BB.
  • La diagonale de M2M^2 redonne les degrés 22, 33, 33, 22 : une chaîne de longueur 2 de ii à ii est un aller-retour vers un voisin.
  • Pour NN, le coefficient ligne PP, colonne RR de N2N^2 vaut 11 : un seul chemin de longueur 2, P→Q→RP\to Q\to R.

Démonstration (à savoir refaire)

On raisonne par récurrence. Pour n⩾1n\geqslant1, on note P(n)\mathcal{P}(n) : « pour tous sommets ii et jj, le coefficient (Mn)ij(M^n)_{ij} est le nombre de chaînes de longueur nn de ii à jj ».

Initialisation. Une chaîne de longueur 1 de ii à jj est une arête entre ii et jj : il y en a une si ii et jj sont adjacents, aucune sinon. Ce nombre est mijm_{ij}, coefficient de M1=MM^1=M : P(1)\mathcal{P}(1) est vraie.

Hérédité. Soit n⩾1n\geqslant1 tel que P(n)\mathcal{P}(n) est vraie. Une chaîne de longueur n+1n+1 de ii à jj se découpe selon son avant-dernier sommet kk : c'est une chaîne de longueur nn de ii à kk, suivie d'une arête entre kk et jj. Pour kk fixé, il y a (Mn)ik(M^n)_{ik} débuts possibles, par hypothèse de récurrence, et mkjm_{kj} arêtes finales possibles, soit (Mn)ik×mkj(M^n)_{ik}\times m_{kj} chaînes. Deux chaînes d'avant-derniers sommets différents sont différentes, donc on additionne sur kk ; par définition du produit de deux matrices :

∑k=1p(Mn)ik mkj=(Mn×M)ij=(Mn+1)ij.\sum_{k=1}^{p}(M^n)_{ik}\,m_{kj}=(M^n\times M)_{ij}=(M^{n+1})_{ij}.

Donc P(n+1)\mathcal{P}(n+1) est vraie.

Conclusion. P(n)\mathcal{P}(n) est vraie pour tout entier n⩾1n\geqslant1. Pour un graphe orienté, la preuve est la même en remplaçant « arête » par « arc » et « chaîne » par « chemin ».

Les pièges

  • Ordre ou nombre d'arêtes ? L'ordre compte les sommets : GG est d'ordre 4, avec 5 arêtes.
  • Longueur d'une chaîne. Elle compte les arêtes, pas les sommets : AA–BB–DD est de longueur 2.
  • Connexe ou complet ? Connexe demande une chaîne entre deux sommets quelconques, complet une arête : GG est connexe sans être complet.
  • Sens des arcs. La ligne est le départ, la colonne l'arrivée : en les inversant, tu comptes les chemins de jj vers ii. Annonce toujours l'ordre des sommets.
  • Puissance d'une matrice. M2M^2 est le produit M×MM\times M, pas le carré de chaque coefficient, qui redonnerait MM.
  • Longueur exacte. MnM^n compte les chaînes de longueur nn exactement, pas « au plus nn ».

Ce qu'il faut retenir

  • Ordre : nombre de sommets ; degré d'un sommet : nombre de ses voisins.
  • KnK_n : tous les sommets de degré n−1n-1 et n(n−1)2\dfrac{n(n-1)}{2} arêtes.
  • Longueur d'une chaîne : nombre d'arêtes. Connexe : deux sommets quelconques sont reliés par une chaîne.
  • mij=1m_{ij}=1 si ii et jj sont adjacents (arc de ii vers jj si le graphe est orienté), 00 sinon.
  • Graphe non orienté : MM symétrique, diagonale nulle, somme de la ligne ii égale au degré de ii.
  • Le coefficient ligne ii, colonne jj de MnM^n est le nombre de chaînes (ou de chemins) de longueur nn de ii à jj.
  • Ce résultat se démontre par récurrence, en découpant une chaîne de longueur n+1n+1 selon son avant-dernier sommet.

À l'épreuve

Un exercice peut partir d'une situation concrète : réseau, plan, tournoi, relations entre personnes. Consignes possibles :

  • « Modélise la situation par un graphe », puis donne son ordre et ses degrés.
  • « Le graphe est-il connexe ? complet ? » : justifie par des chaînes, ou par deux sommets non reliés.
  • « Écris la matrice d'adjacence », dans l'ordre des sommets imposé.
  • « Combien de chemins de longueur 3 relient XX à YY ? » : M2M^2 se calcule à la main, une puissance plus grande peut être fournie. Cite le théorème, désigne le coefficient lu et conclus par une phrase.
  • La démonstration par récurrence, en entier ou par étapes.

Les erreurs à éviter : une matrice sans ordre des sommets annoncé, un nombre lu dans M3M^3 sans citer le théorème, une longueur comptée en sommets.

À retenir

  • Lire un graphe : sommets, arêtes, ordre, degré

    Un graphe est formé de sommets et d'arêtes reliant certains d'entre eux ; seules comptent les paires reliées.Deux sommets reliés par une arête sont adjacents (voisins).L'ordre du graphe est son nombre de sommets, pas son nombre d'arêtes.Le degré d'un sommet est son nombre de voisins, c'est-à-dire le nombre d'arêtes dont il est une extrémité.
  • Reconnaître le graphe complet et compter ses arêtes

    Un graphe d'ordre nn est complet si deux sommets distincts quelconques sont toujours adjacents ; on le note KnK_n.Dans KnK_n, chaque sommet est de degré n−1n-1.KnK_n a n(n−1)2\dfrac{n(n-1)}{2} arêtes : n(n−1)n(n-1) extrémités, chaque arête comptée deux fois.Un tournoi où chacun rencontre une fois chacun des autres se modélise par un graphe complet.
  • Suivre une chaîne et tester la connexité

    Une chaîne est une suite de sommets dont deux consécutifs sont adjacents ; elle peut repasser par un sommet.Sa longueur est son nombre d'arêtes, soit le nombre de sommets de la suite moins 1.Un graphe est connexe si deux sommets quelconques sont reliés par une chaîne.Pour prouver qu'il ne l'est pas, exhibe deux sommets qu'aucune chaîne ne relie.
  • Traduire une situation en graphe

    Choisis les sommets (les objets) et la relation qui se traduit par une arête.Si la relation a un sens (rue à sens unique, « suit »), prends un graphe orienté : des arcs, des chemins.Traduis la question : nombre de liens d'un objet = degré, aller de partout à partout = connexité, trajets enchaînés = chaîne.
  • Écrire la matrice d'adjacence d'un graphe

    Numérote les sommets une fois pour toutes : mij=1m_{ij}=1 si ii et jj sont adjacents, 00 sinon.Graphe orienté : mij=1m_{ij}=1 s'il existe un arc de ii vers jj ; la ligne est le départ, la colonne l'arrivée.Graphe non orienté : MM est symétrique et sa diagonale est nulle.La somme de la ligne ii est le degré du sommet ii.
  • Compter les chemins avec les puissances de M

    Le coefficient ligne ii, colonne jj de MnM^n est le nombre de chaînes (de chemins si le graphe est orienté) de longueur nn de ii à jj.M2=M×MM^2=M\times M se calcule ligne par colonne, jamais en élevant chaque coefficient au carré.Pour un graphe non orienté, la diagonale de M2M^2 donne les degrés.Un coefficient nul : aucune chaîne de cette longueur exacte.
  • Démontrer la formule des chemins

    Récurrence sur n⩾1n\geqslant1, avec P(n)\mathcal{P}(n) : « (Mn)ij(M^n)_{ij} est le nombre de chaînes de longueur nn de ii à jj ».Initialisation : une chaîne de longueur 1 est une arête, comptée par mijm_{ij}.Hérédité : une chaîne de longueur n+1n+1 est une chaîne de longueur nn de ii à kk, suivie d'une arête de kk à jj.On somme sur l'avant-dernier sommet kk : ∑k(Mn)ik mkj=(Mn+1)ij\sum_{k}(M^n)_{ik}\,m_{kj}=(M^{n+1})_{ij}.

Teste-toi

Trois questions. Réponds, la correction s’affiche.

Question 1 sur 3
Le graphe FF a pour sommets 1,2,3,4,51, 2, 3, 4, 5 et pour arêtes 11–22, 11–33, 11–44, 22–33, 33–44, 44–55. Quel est l'ordre de FF ?

Correction

L'ordre est le nombre de sommets : 1,2,3,4,51, 2, 3, 4, 5, soit 5.Les arêtes 11–22, 11–33, 11–44, 22–33, 33–44, 44–55 sont au nombre de 6, ce qui n'est pas l'ordre.Erreur classique : répondre 6 — on compte les arêtes alors que l'ordre compte les sommets.
Question 2 sur 3
Un réseau de transport relie des stations par des lignes directes, sans sens imposé. Pour le modéliser par un graphe, quel choix est correct ?

Correction

On choisit comme sommets les objets étudiés : ici les stations.Une arête traduit la relation « est reliée directement à » : une ligne directe entre deux stations.Erreur classique : prendre les lignes comme sommets — une ligne n'est pas un objet que l'on relie, c'est le lien entre deux stations.
Question 3 sur 3
Dans la démonstration par récurrence du théorème sur les puissances de la matrice d'adjacence MM, quelle est la propriété P(n)\mathcal{P}(n) à démontrer ?

Correction

P(n)\mathcal{P}(n) : « pour tous sommets ii et jj, (Mn)ij(M^n)_{ij} est le nombre de chaînes de longueur nn de ii à jj ».Les mots « pour tous sommets » comptent : l'hérédité utilise P(n)\mathcal{P}(n) pour les couples (i,k)(i,k), pas seulement pour (i,j)(i,j).Erreur classique : croire que (Mn)ij=(mij)n(M^n)_{ij}=(m_{ij})^n — la puissance d'une matrice est un produit matriciel, pas la puissance de chaque coefficient.

Dans Insight, ce chapitre a 119 questions, et l’app te les repose au bon moment pour que tu ne les oublies pas avant le bac.

Contenu préparé avec l’aide d’outils d’IA, vérifié.

Réviser ce chapitre gratuitement