Aller au contenu
OptiTAB

Maths Terminale · Chapitre 24 · Maths Expertes

Graphes et matrices

  • 9 parties
  • 12 schémas
  • Lecture ≈ 29 min
  • Conforme au programme
Objectifs

Calculer avec des matrices (produit, inverse, puissances), résoudre un système linéaire et étudier une suite de matrices colonnes ; modéliser une situation par un graphe et compter des chemins avec la matrice d’adjacence ; étudier une chaîne de Markov à deux ou trois états. Programme de Mathématiques expertes.

IMatrices

DéfinitionMatrice

Soient m et n deux entiers naturels non nuls. Une matrice de taille m×n est un tableau de nombres réels à m lignes et n colonnes. Le coefficient aij est situé à la ligne i et à la colonne j ; on note A=(aij).

  • Matrice ligne : une seule ligne (taille 1×n).
  • Matrice colonne : une seule colonne (taille m×1).
  • Matrice carrée d’ordre n : n lignes et n colonnes.
Exemple

A=(123456) est de taille 2×3 et a23=6 (ligne 2, colonne 3). X=(10−1) est une matrice colonne de taille 3×1 et L=(1234) une matrice ligne de taille 1×4.

DéfinitionMatrices carrées particulières
  • La matrice nulle 0n : tous ses coefficients sont nuls.
  • La matrice identité In : des 1 sur la diagonale, des 0 ailleurs ; par exemple I2=(1001) et I3=(100010001).
  • Une matrice diagonale : ses coefficients hors de la diagonale sont nuls, par exemple D=(2003).

Deux matrices sont égales lorsqu’elles ont la même taille et les mêmes coefficients, place par place.

IIOpérations sur les matrices

Somme et produit par un réel

Définition

Pour deux matrices A et B de même taille et un réel k, on calcule coefficient par coefficient :

(A+B)ij=aij+bijet(kA)ij=kaij
Exemple
(123456)+(2−1031−2)=(313764)
3(12−14)=(36−312)

Produit de deux matrices

DéfinitionProduit

Soit A de taille m×n et B de taille n×p : le nombre de colonnes de A est égal au nombre de lignes de B. Le produit AB est la matrice de taille m×p définie par

(AB)ij=ai1b1j+ai2b2j+⋯+ainbnj=∑k=1naikbkj
MéthodeCalculer un coefficient de AB

Le coefficient (AB)ij se calcule avec la ligne i de A et la colonne j de B : on multiplie leurs termes deux à deux, puis on additionne.

Produit de matrices : la ligne 2 de A et la colonne 1 de B donnent le coefficient (AB)21 = 11
Exemple

Avec A=(123456) (taille 2×3) et B=(10−1221) (taille 3×2), le produit AB existe et il est de taille 2×2 :

(AB)11=1×1+2×(−1)+3×2=5(AB)12=1×0+2×2+3×1=7(AB)21=4×1+5×(−1)+6×2=11(AB)22=4×0+5×2+6×1=16

donc AB=(571116).

PropriétéRègles de calcul

Pour des matrices de tailles compatibles :

  • (AB)C=A(BC) (associativité) ;
  • A(B+C)=AB+AC et (A+B)C=AC+BC (distributivité) ;
  • AIn=InA=A pour toute matrice carrée A d’ordre n.
AttentionLe produit n’est pas commutatif

En général AB≠BA. Avec A=(1234) et B=(5678) :

AB=(19224350)maisBA=(23343146)

De plus, un produit peut être nul sans qu’aucun des facteurs ne le soit : (1111)(1−1−11)=02.

IIIMatrice inverse et systèmes linéaires

Matrice inverse

Définition

Une matrice carrée A d’ordre n est inversible s’il existe une matrice carrée B d’ordre n telle que AB=BA=In. Cette matrice B est unique : c’est l’inverse de A, notée A−1.

PropriétéUne seule égalité suffit (admis)

Si A et B sont deux matrices carrées d’ordre n telles que AB=In, alors A est inversible et A−1=B.

ThéorèmeInverse d’une matrice d’ordre 2

Soit A=(abcd). Le nombre det(A)=ad−bc est le déterminant de A.

  • Si ad−bc≠0, A est inversible et A−1=1ad−bc(d−b−ca).
  • Si ad−bc=0, A n’est pas inversible.
Démonstration

Posons B=(d−b−ca). Un calcul direct donne

AB=(ad−bc−ab+bacd−dc−cb+da)=(ad−bc)I2
  • Si ad−bc≠0 : A×1ad−bcB=I2, donc A est inversible d’inverse 1ad−bcB.
  • Si ad−bc=0 : AB=02. Si A était inversible, on aurait B=A−1(AB)=02, donc a=b=c=d=0 et A=02, qui n’est pas inversible : c’est absurde.
Exemple

Pour A=(2314) : det(A)=2×4−3×1=5≠0, donc

A−1=15(4−3−12)

Contrôle : (2314)(4−3−12)=(5005)=5I2, donc AA−1=I2.

MéthodeInverse d’une matrice d’ordre 3

On obtient l’inverse à la calculatrice (ou avec un logiciel), puis on le contrôle par un produit. Par exemple, pour T=(110011001) et T′=(1−1101−1001), on vérifie que TT′=I3 : donc T−1=T′.

Attention

On ne divise jamais par une matrice : l’écriture 1A n’a pas de sens. On multiplie par A−1, du bon côté. Si A et B sont inversibles, (AB)−1=B−1A−1 : l’ordre s’inverse.

RemarquePour aller plus loin (hors programme) : déterminant d’ordre 3

Pour A=(abcdefghi), on définit

det(A)=aei+bfg+cdh−ceg−afh−bdi

La règle de Sarrus permet de retrouver cette formule : on recopie les deux premières colonnes à droite du tableau, on additionne les produits des trois diagonales descendantes et on retranche ceux des trois diagonales montantes. Comme à l’ordre 2, A est inversible si et seulement si det(A)≠0.

Règle de Sarrus : trois diagonales descendantes comptées avec le signe plus, trois diagonales montantes avec le signe moins

Écriture matricielle d’un système linéaire

Définition

Un système de n équations linéaires à n inconnues s’écrit AX=Y, où A est la matrice carrée des coefficients, X la matrice colonne des inconnues et Y la matrice colonne des seconds membres.

Théorème

Si A est inversible, le système AX=Y admet une unique solution :

X=A−1Y
Démonstration

Si AX=Y, en multipliant à gauche par A−1 : A−1AX=A−1Y, c’est-à-dire X=A−1Y. Réciproquement, X=A−1Y vérifie AX=AA−1Y=Y.

Exemple

Le système {2x+3y=5x+4y=6 s’écrit AX=Y avec A=(2314), X=(xy) et Y=(56). On a vu que A−1=15(4−3−12), donc

X=A−1Y=15(4×5+(−3)×6(−1)×5+2×6)=15(27)

L’unique solution est x=25 et y=75.

ExempleUn système de trois équations

Le système {x+y=3y+z=5z=2 s’écrit TX=(352) avec la matrice T ci-dessus. Donc

X=T−1(352)=(3−5+25−22)=(032)
Attention

Si A n’est pas inversible, le système a soit aucune solution, soit une infinité de solutions : on le résout alors par combinaison ou par substitution.

IVPuissances de matrices et suites

Puissances d’une matrice carrée

Définition

Pour une matrice carrée A d’ordre p et un entier n≥1, An=A×A×⋯×A (n facteurs), avec la convention A0=Ip. Pour tout n, An+1=An×A=A×An.

PropriétéMatrice diagonale

Pour D=(a00b) et tout entier n≥0, Dn=(an00bn) (de même à l’ordre 3).

Attention

Sauf pour une matrice diagonale, on n’obtient pas An en élevant chaque coefficient à la puissance n.

MéthodeCalculer An
  1. Calculer A2, A3, A4 (à la main ou à la calculatrice).
  2. Conjecturer une formule pour An.
  3. La démontrer par récurrence, en utilisant An+1=An×A.
Exemple

Soit A=(1101). On trouve A2=(1201) et A3=(1301) : on conjecture que An=(1n01) pour tout entier n≥0.

  • Initialisation : A0=I2=(1001), la formule est vraie pour n=0.
  • Hérédité : si An=(1n01), alors An+1=AnA=(1n01)(1101)=(1n+101).

Suites de matrices colonnes

Théorème

Soit A une matrice carrée et (Un) une suite de matrices colonnes telle que Un+1=AUn pour tout entier n. Alors, pour tout entier n≥0 :

Un=AnU0
Démonstration

Par récurrence : U0=IU0=A0U0 ; si Un=AnU0, alors Un+1=AUn=AAnU0=An+1U0.

ExempleÉcrire une suite récurrente sous forme matricielle

La suite définie par u0=0, u1=1 et un+2=un+1+2un s’étudie avec Un=(un+1un) :

Un+1=(un+2un+1)=(1210)(un+1un)

donc Un=(1210)nU0 avec U0=(10).

MéthodeSuite Un+1=AUn+C
  1. Chercher une matrice colonne constante L telle que L=AL+C, c’est-à-dire (I−A)L=C ; si I−A est inversible, L=(I−A)−1C.
  2. Poser Vn=Un−L : alors Vn+1=AUn+C−(AL+C)=AVn, donc Vn=AnV0.
  3. Conclure : Un=An(U0−L)+L.
Exemple

A=(0,5000,25), C=(13) et U0=(00). L’équation (I2−A)L=C s’écrit 0,5ℓ1=1 et 0,75ℓ2=3, donc L=(24). Alors

Un=An(U0−L)+L=(2−2×0,5n4−4×0,25n)

Comme 0,5n et 0,25n tendent vers 0, les coordonnées de Un tendent vers 2 et 4.

VTransformations géométriques du plan

Propriété

Dans un repère orthonormé d’origine O, chacune des transformations ci-dessous envoie le point M(x;y) sur le point M′(x′;y′) tel que (x′y′)=A(xy).

TransformationMatrice A
Rotation de centre O et d’angle θ(cos⁡θ−sin⁡θsin⁡θcos⁡θ)
Symétrie d’axe (Ox)(100−1)
Symétrie d’axe (Oy)(−1001)
Homothétie de centre O et de rapport k(k00k)
Exemple

La rotation de centre O et d’angle π2 a pour matrice R=(0−110), car cos⁡π2=0 et sin⁡π2=1. L’image de M(2;1) est M′(−1;2), car (0−110)(21)=(−12).

Rotation de centre O et d'angle pi sur 2 : le point M(2 ; 1) a pour image M'(-1 ; 2)
AttentionComposer deux transformations

Appliquer d’abord la transformation de matrice A, puis celle de matrice B, revient à appliquer la matrice BA (et non AB) : X″=B(AX)=(BA)X.

VIGraphes

Vocabulaire

DéfinitionGraphe

Un graphe (non orienté) est formé de sommets et d’arêtes ; chaque arête relie deux sommets distincts, et deux sommets sont reliés par au plus une arête. Deux sommets reliés par une arête sont adjacents.

  • L’ordre du graphe est son nombre de sommets.
  • Le degré d’un sommet est le nombre d’arêtes dont il est une extrémité.
  • Un graphe est complet si deux sommets distincts quelconques sont toujours adjacents.
Graphe non orienté G à cinq sommets A, B, C, D, E et sept arêtes
Exemple

Le graphe G est d’ordre 5 et possède 7 arêtes. A et B sont adjacents ; A et C ne le sont pas, donc G n’est pas complet.

SommetABCDE
Degré23342
Propriété

La somme des degrés des sommets d’un graphe est égale au double du nombre d’arêtes.

Démonstration

Chaque arête a deux extrémités : elle est comptée une fois dans le degré de chacune d’elles, donc deux fois dans la somme des degrés. Pour G : 2+3+3+4+2=14=2×7.

PropriétéGraphe complet

Dans le graphe complet Kn à n sommets, chaque sommet est de degré n−1 ; la somme des degrés vaut n(n−1), donc Kn possède n(n−1)2 arêtes.

Graphes complets K4 (6 arêtes) et K5 (10 arêtes)

Chaînes et connexité

Définition
  • 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. Les sommets et les arêtes peuvent se répéter.
  • Une chaîne est fermée si son premier et son dernier sommet sont égaux ; un cycle est une chaîne fermée dont les arêtes sont toutes distinctes.
  • Un graphe est connexe si deux sommets quelconques peuvent toujours être reliés par une chaîne.
Exemple

Dans G, A−B−C−E est une chaîne de longueur 3 et B−C−D−B est un cycle de longueur 3. Le graphe G est connexe ; si on lui retire les arêtes C−E et D−E, le sommet E est isolé et le graphe obtenu n’est plus connexe.

Le graphe G est connexe ; sans les arêtes C-E et D-E, le sommet E est isolé et le graphe n'est plus connexe

Graphes orientés, graphes pondérés

Définition
  • Dans un graphe orienté, les arêtes ont un sens : ce sont des arcs. Un chemin est une suite de sommets dans laquelle chaque sommet est relié au suivant par un arc ; sa longueur est son nombre d’arcs.
  • Dans un graphe pondéré, chaque arête (ou arc) porte un nombre, son poids : distance, durée, coût, probabilité…
Exemple

Le graphe pondéré ci-dessous donne les durées de trajet, en minutes, entre cinq villages. La chaîne A−B−D−E a pour poids 3+9+12=24 et la chaîne A−D−E a pour poids 7+12=19 : elle est plus rapide.

Graphe pondéré : durées de trajet en minutes entre les villages A, B, C, D et E

VIIMatrice d’adjacence et nombre de chemins

Définition

Soit un graphe d’ordre p dont les sommets sont numérotés de 1 à p. Sa matrice d’adjacence est la matrice carrée M d’ordre p dont le coefficient mij vaut 1 si une arête relie i et j (si un arc va de i vers j, pour un graphe orienté), et 0 sinon.

Propriété
  • Pour un graphe non orienté, M est symétrique (mij=mji) et la somme de la ligne i est le degré du sommet i.
  • Pour un graphe orienté, la somme de la ligne i est le nombre d’arcs qui partent du sommet i.
  • Sans boucle, la diagonale de M ne contient que des 0.
ExempleGraphe non orienté

Dans l’ordre A, B, C, D, E, la matrice d’adjacence du graphe G est

MG=(0101010110010111110100110)

Elle est symétrique ; la ligne de D contient quatre 1 : D est de degré 4.

Graphe orienté H : arcs A vers B, B vers C, C vers A, A vers D, C vers D et D vers B
ExempleGraphe orienté

Le graphe orienté H a pour arcs A→B, B→C, C→A, A→D, C→D et D→B. Dans l’ordre A, B, C, D :

M=(0101001010010100)

Elle n’est pas symétrique : il y a un arc A→B mais pas d’arc B→A.

ThéorèmeNombre de chemins de longueur n

Soit M la matrice d’adjacence d’un graphe et n≥1 un entier. Le coefficient (Mn)ij est égal au nombre de chemins de longueur n (de chaînes de longueur n pour un graphe non orienté) qui vont du sommet i au sommet j.

Démonstration

Par récurrence sur n. Pour n=1, c’est la définition de M.

Supposons la propriété vraie pour un entier n≥1. Un chemin de longueur n+1 de i à j est formé d’un chemin de longueur n de i à un sommet k (son avant-dernier sommet), suivi d’un arc de k vers j. Pour k fixé, il y a (Mn)ik chemins de i à k, et chacun se prolonge de mkj façons (1 si l’arc k→j existe, 0 sinon) : cela fait (Mn)ikmkj chemins. Les cas k=1,…,p ne se recouvrent pas, donc le nombre total est

∑k=1p(Mn)ikmkj=(MnM)ij=(Mn+1)ij
ExempleInterpréter M2

Pour le graphe orienté H :

M2=(0110100102010010)

Le coefficient ligne C, colonne B vaut 2 : il y a deux chemins de longueur 2 de C vers B, C→A→B et C→D→B. Le coefficient ligne B, colonne B est nul : aucun chemin de longueur 2 ne part de B pour y revenir.

Les deux chemins de longueur 2 de C vers B, en vert : C-A-B et C-D-B
MéthodeCalculer rapidement une ligne de M2

La ligne i de M2 est la somme des lignes de M des sommets atteints depuis i par un arc. Dans H, de C partent les arcs C→A et C→D : la ligne C de M2 est la somme des lignes A et D de M, soit (0101)+(0100)=(0201).

RemarquePour aller plus loin : connexité et matrice

Un graphe d’ordre p est connexe si et seulement si tous les coefficients de Ip+M+M2+⋯+Mp−1 sont strictement positifs : deux sommets reliés par une chaîne le sont par une chaîne de longueur au plus p−1. Pour un graphe orienté, cette condition signifie que l’on peut aller de tout sommet à tout autre par un chemin : on dit que le graphe est fortement connexe.

Attention
  • Les coefficients de Mn comptent les chemins de longueur exactement n, sommets répétés compris.
  • On fixe l’ordre des sommets avant d’écrire M : ligne = départ, colonne = arrivée.
  • Les puissances de la matrice des poids d’un graphe pondéré ne comptent pas les chemins.

VIIIChaînes de Markov

Matrice de transition et graphe

Définition

Un système peut se trouver dans deux ou trois états ; on note Xn son état à l’étape n (n=0,1,2,…). La suite (Xn) est une chaîne de Markov si la probabilité de passer de l’état i à l’état j ne dépend que de i et de j (ni de n, ni des états antérieurs). On note

pij=P(Xn=i)(Xn+1=j)

La matrice de transition est P=(pij) : la ligne i correspond à l’état de départ, la colonne j à l’état d’arrivée. Le graphe pondéré associé a un sommet par état et un arc i→j de poids pij lorsque pij≠0 (une boucle si i=j).

Propriété

Les coefficients de P sont positifs ou nuls et la somme des coefficients de chaque ligne vaut 1 : sur le graphe, les poids des arcs qui partent d’un sommet, boucle comprise, ont pour somme 1.

ExempleDeux états

Chaque semaine, un abonné utilise l’une de deux plateformes A et B. S’il est sur A, il y reste la semaine suivante avec la probabilité 0,8 ; s’il est sur B, il passe sur A avec la probabilité 0,3. Dans l’ordre A, B :

P=(0,80,20,30,7)
Graphe probabiliste à deux états A et B avec les probabilités de transition 0,8 ; 0,2 ; 0,3 ; 0,7

Distribution après n transitions

Définition

La distribution à l’étape n est la matrice ligne πn des probabilités des états ; pour deux états, πn=(P(Xn=A)P(Xn=B)). La matrice π0 est la distribution initiale.

Théorème

Pour tout entier n≥0 :

  • πn+1=πnP, donc πn=π0Pn ;
  • le coefficient (Pn)ij est la probabilité de passer de l’état i à l’état j en n transitions : (Pn)ij=P(X0=i)(Xn=j).
Démonstration

Les événements (Xn=k), pour les différents états k, forment une partition. D’après la formule des probabilités totales, P(Xn+1=j) est la somme, sur tous les états k, des produits P(Xn=k)×P(Xn=k)(Xn+1=j). Comme P(Xn=k)(Xn+1=j)=pkj :

P(Xn+1=j)=∑kP(Xn=k)pkj

C’est le coefficient j de la matrice ligne πnP : donc πn+1=πnP, et par récurrence πn=π0Pn.

Si la chaîne part de l’état i avec certitude, π0 a un 1 en position i et des 0 ailleurs : πn=π0Pn est alors la ligne i de Pn, et son coefficient j est (Pn)ij.

Exemple

L’abonné est sur A au départ : π0=(10). Alors

π1=π0P=(0,80,2)

Pour π2=π1P, on calcule ses deux coefficients :

0,8×0,8+0,2×0,3=0,70,8×0,2+0,2×0,7=0,3

donc π2=(0,70,3).

La probabilité qu’il soit sur A deux semaines plus tard est 0,7 : c’est aussi le coefficient (P2)AA, car P2=(0,70,30,450,55).

Attention

La distribution est une matrice ligne, placée à gauche de P : πn+1=πnP, et non Pπn.

Distribution invariante

Définition

Une distribution π (matrice ligne à coefficients positifs ou nuls, de somme 1) est invariante si πP=π : si la chaîne a la distribution π à une étape, elle la garde à toutes les étapes suivantes.

MéthodeDéterminer une distribution invariante

On pose π=(pq) (ou π=(abc) pour trois états), on écrit le système πP=π et on lui ajoute l’équation p+q=1 (ou a+b+c=1).

Exemple

Pour P=(0,80,20,30,7), la première équation de πP=π est 0,8p+0,3q=p, soit 0,3q=0,2p, c’est-à-dire q=23p (la seconde équation donne la même condition). Avec p+q=1 : 53p=1, donc p=0,6 et q=0,4. La distribution invariante est π=(0,60,4).

ExempleÉvolution à long terme

Avec an=P(Xn=A), on a P(Xn=B)=1−an, donc

an+1=0,8an+0,3(1−an)=0,5an+0,3

Ainsi an+1−0,6=0,5(an−0,6) : la suite (an−0,6) est géométrique de raison 0,5 et an=0,6+(a0−0,6)×0,5n. Comme 0,5n tend vers 0, an tend vers 0,6 : quelle que soit la distribution initiale, πn se rapproche de la distribution invariante (0,60,4).

Probabilités a_n d'être en A : depuis A ou depuis B, elles se rapprochent de 0,6
ExempleTrois états

Un pion se déplace sur trois cases alignées A, B, C. Depuis A (ou depuis C), il reste sur place ou va en B, avec la probabilité 0,5 chaque fois ; depuis B, il reste en B avec la probabilité 0,5 et va en A ou en C avec la probabilité 0,25 chaque fois. Dans l’ordre A, B, C :

P=(0,50,500,250,50,2500,50,5)

Avec π=(abc), le système πP=π s’écrit

{0,5a+0,25b=a0,5a+0,5b+0,5c=b0,25b+0,5c=c

La première équation donne b=2a, la troisième b=2c. Avec a+b+c=1 : a+2a+a=1, donc a=c=0,25 et b=0,5 (la deuxième équation est alors vérifiée). La distribution invariante est (0,250,50,25).

Graphe probabiliste à trois états A, B, C alignés, avec boucles et probabilités 0,5 et 0,25

Calcul avec Python

Le programme suivant calcule πn=π0Pn en appliquant n fois la relation πk+1=πkP (les listes représentent les matrices ligne par ligne).

Python
def distrib(pi, P, n):
    k = len(P)
    for _ in range(n):
        pi = [sum(pi[i] * P[i][j]
              for i in range(k))
              for j in range(k)]
    return pi

P = [[0.8, 0.2],
     [0.3, 0.7]]
pi = distrib([1, 0], P, 2)
print([round(p, 4)
       for p in pi])
# affiche [0.7, 0.3]

Avec n=20, le programme affiche [0.6, 0.4] : on retrouve la distribution invariante.

IXL’essentiel

À retenir
  • (AB)ij : ligne i de A par colonne j de B ; en général AB≠BA.
  • Si ad−bc≠0, (abcd)−1=1ad−bc(d−b−ca) ; si A est inversible, AX=Y⟺X=A−1Y.
  • Un+1=AUn donne Un=AnU0 ; pour Un+1=AUn+C, on cherche L=AL+C, puis Un=An(U0−L)+L.
  • (Mn)ij est le nombre de chemins de longueur n de i à j.
  • Chaîne de Markov : πn=π0Pn ; distribution invariante : πP=π, avec des coefficients de somme 1.
AttentionErreurs fréquentes
  • Multiplier des matrices de tailles incompatibles, ou dans le mauvais ordre.
  • Écrire 1A ou « diviser » par une matrice.
  • Calculer An en élevant chaque coefficient à la puissance n (faux, sauf pour une matrice diagonale).
  • Inverser lignes et colonnes dans une matrice d’adjacence ou de transition : ligne = départ.
  • Oublier une boucle dans un graphe de Markov : les poids qui partent de chaque sommet ont pour somme 1.

Cours lu ? Continue avec :

Plateforme OptiTAB

S’entraîner jusqu’à maîtriser le programme de Terminale

Les 12 exercices corrigés de ce chapitre, le suivi de tes progrès et des révisions guidées.

Découvrir l’abonnement

Cours particuliers

Un prof de maths en Terminale, en ligne

Des séances individuelles avec un professeur, à distance, pour comprendre, combler ses lacunes et préparer les contrôles et le bac.

Réserver un cours particulier