Graphes et Matrices

Cours complet · mathématiques expertes (terminale), chapitre 4 · terminale, option mathématiques expertes

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

Les graphes modélisent les réseaux (routiers, sociaux, informatiques) et les matrices donnent un calcul efficace sur ces modèles. Ce chapitre introduit les deux notions, les fait interagir (matrice d'adjacence, nombre de chemins), puis les applique aux suites récurrentes et aux chaînes de Markov.

4.1 Graphes

Définition 4.1Graphe

Un graphe est constitué d'un ensemble fini de sommets et d'un ensemble d'arêtes, chaque arête reliant deux sommets. Deux sommets reliés par une arête sont dits adjacents.

L'ordre du graphe est son nombre de sommets.
Le degré d'un sommet est le nombre d'arêtes qui lui sont incidentes.
Un graphe est complet si deux sommets quelconques sont toujours adjacents.
Une chaîne est une suite de sommets consécutivement adjacents ; sa longueur est son nombre d'arêtes. Un graphe est connexe si deux sommets quelconques sont toujours reliés par une chaîne.

Dans un graphe orienté, les arêtes (appelées arcs) ont un sens ; dans un graphe pondéré, chaque arête porte un nombre (distance, coût, probabilité...).

4.2 Matrices

4.2.1 Définitions et opérations

Définition 4.2Matrice

Une matrice de taille $n \times p$ est un tableau de nombres réels à $n$ lignes et $p$ colonnes. On note $a_{ij}$ le coefficient situé à la ligne $i$ et la colonne $j$ . Une matrice est carrée si $n = p$ , ligne si $n = 1$ , colonne si $p = 1$ . La matrice identité $I_{n}$ est la matrice carrée avec des $1$ sur la diagonale et des $0$ ailleurs.

Définition 4.3Opérations

Somme (matrices de même taille) et multiplication par un réel : coefficient par coefficient.
Produit : si $A$ est de taille $n \times p$ et $B$ de taille $p \times q$ , le produit $A B$ est la matrice $n \times q$ de coefficients :

$(A B)_{ij} = k = 1 \sum p a_{ik} b_{k j}$

(ligne $i$ de $A$ « contre » colonne $j$ de $B$ ). Attention : en général $A B \neq = B A$ .

Puissances d'une matrice carrée : $A^{n} = A \times A \times \dots \times A$ ( $n$ facteurs), avec $A^{0} = I$ .

Exemple 4.4Produit de matrices

2 \times 2

$(1324) (05 1 - 1) = (1 \times 0 + 2 \times 5 3 \times 0 + 4 \times 5 1 \times 1 + 2 \times (- 1) 3 \times 1 + 4 \times (- 1)) = (1020 - 1 - 1)$

4.2.2 Inverse d'une matrice carrée

Définition 4.5Matrice inverse

Une matrice carrée $A$ est inversible s'il existe une matrice $A^{- 1}$ (l'inverse) telle que :

$A A^{- 1} = A^{- 1} A = I$

Proposition 4.6Inverse d'une matrice

2 \times 2

La matrice $A = (a c b d)$ est inversible si et seulement si son déterminant $det (A) = a d - b c$ est non nul, et dans ce cas :

$A^{- 1} = \frac{1}{a d - b c} (d - c - b a)$

Proposition 4.7Application aux systèmes linéaires

Le système linéaire ${a x + b y = e c x + d y = f$ s'écrit matriciellement $A X = B$ avec $X = (x y)$ et $B = (e f)$ . Si $A$ est inversible, l'unique solution est :

$X = A^{- 1} B$

4.3 Matrice d'Adjacence et Nombre de Chemins

Définition 4.8Matrice d'adjacence

Soit un graphe (orienté ou non) dont les sommets sont numérotés $1, 2, \dots, n$ . Sa matrice d'adjacence est la matrice carrée $A$ de taille $n$ dont le coefficient $a_{ij}$ vaut le nombre d'arêtes (ou d'arcs) allant du sommet $i$ au sommet $j$ . Pour un graphe non orienté, $A$ est symétrique ( $a_{ij} = a_{j i}$ ).

◆Théorème 4.9Nombre de chemins de longueur

n

Soit $A$ la matrice d'adjacence d'un graphe. Pour tout entier $n \geq 1$ , le coefficient $(i, j)$ de la puissance $A^{n}$ est égal au nombre de chemins de longueur $n$ allant du sommet $i$ au sommet $j$ .

Démonstration ((exigible) — par récurrence sur

n

)

Initialisation : pour $n = 1$ , $a_{ij}$ est par définition le nombre d'arêtes de $i$ à $j$ , c'est-à-dire le nombre de chemins de longueur $1$ . Hérédité : supposons que le coefficient $(i, k)$ de $A^{n}$ , noté $a_{ik}^{(n)}$ , compte les chemins de longueur $n$ de $i$ à $k$ . Un chemin de longueur $n + 1$ de $i$ à $j$ est constitué d'un chemin de longueur $n$ de $i$ vers un sommet intermédiaire $k$ , suivi d'une arête de $k$ à $j$ . En sommant sur tous les intermédiaires possibles :

$nombre de chemins de longueur n + 1 de i a ˋ j = k = 1 \sum n_{sommets} a_{ik}^{(n)} a_{k j}$

qui est exactement le coefficient $(i, j)$ du produit $A^{n} \times A = A^{n + 1}$ . La propriété est héréditaire, donc vraie pour tout $n \geq 1$ .

4.4 Suites de Matrices Colonnes

Proposition 4.10Suites vérifiant

U_{n + 1} = A U_{n} + C

Soit $(U_{n})$ une suite de matrices colonnes vérifiant $U_{n + 1} = A U_{n} + C$ , où $A$ est une matrice carrée et $C$ une matrice colonne constante.

Si $C = 0$ (suite « homogène ») : $U_{n} = A^{n} U_{0}$ .
Sinon, on cherche une matrice colonne constante $K$ telle que $K = A K + C$ (« état stable »). La suite $V_{n} = U_{n} - K$ vérifie alors $V_{n + 1} = A V_{n}$ , d'où :

$U_{n} = A^{n} (U_{0} - K) + K$

C'est la généralisation matricielle des suites arithmético-géométriques du chapitre 1 du livre de spécialité.

4.5 Chaînes de Markov à Deux ou Trois États

4.5.1 Modèle et matrice de transition

Définition 4.11Chaîne de Markov

Un système évolue par étapes entre un petit nombre d'états (deux ou trois), de façon aléatoire : la probabilité de passer de l'état $i$ à l'état $j$ lors d'une étape, notée $p_{ij}$ , ne dépend que de $i$ et $j$ (pas du passé). On parle de chaîne de Markov.

Le graphe orienté pondéré associé porte un arc de $i$ vers $j$ de poids $p_{ij}$ .
La matrice de transition $P$ a pour coefficient $(i, j)$ la probabilité $p_{ij}$ . La somme de chaque ligne vaut $1$ .
La distribution à l'étape $n$ est la matrice ligne $π_{n} = (P (X_{n} = 1), \dots)$ donnant les probabilités des états ; $π_{0}$ est la distribution initiale.

4.5.2 Évolution de la distribution

◆Théorème 4.12Distribution après

n

transitions

Soit une chaîne de Markov de matrice de transition $P$ et de distribution initiale $π_{0}$ .

Le coefficient $(i, j)$ de $P^{n}$ est la probabilité de passer de l'état $i$ à l'état $j$ en $n$ transitions.
La distribution après $n$ transitions est :

$π_{n} = π_{0} P^{n}$

Démonstration ((exigible))

Premier point, par récurrence. Pour $n = 1$ , c'est la définition de $P$ . Supposons le résultat vrai au rang $n$ . Pour aller de $i$ à $j$ en $n + 1$ transitions, on passe par un état intermédiaire $k$ à l'étape $n$ : par la formule des probabilités totales (les événements « être en $k$ à l'étape $n$ » forment une partition) :

$P_{i au d e ˊ part} (X_{n + 1} = j) = k \sum (P^{n})_{ik} P_{i au d e ˊ part} (X_{n} = k) \times transition p_{k j} = k \sum (P^{n})_{ik} p_{k j} = (P^{n + 1})_{ij}$

Second point. De même, $P (X_{n} = j) = \sum_{i} P (X_{0} = i) (P^{n})_{ij}$ , c'est-à-dire exactement le coefficient $j$ du produit ligne-matrice $π_{0} P^{n}$ .

4.5.3 Distribution invariante

Définition 4.13Distribution invariante

Une distribution $π$ (matrice ligne à coefficients positifs de somme $1$ ) est invariante pour la chaîne si :

$π P = π$

Si la chaîne « oublie » sa condition initiale, la suite $(π_{n})$ tend vers cette distribution : c'est l'état d'équilibre du système à long terme.

Exemple 4.14Distribution invariante à deux états

Pour la matrice $P = (0, 85 0, 20 0, 15 0, 80)$ (les opérateurs A et B du problème 2 du chapitre 9 du livre de spécialité !), cherchons $π = (a, 1 - a)$ telle que $π P = π$ :

$0, 85 a + 0, 20 (1 - a) = a ⟺ 0, 20 = 0, 35 a ⟺ a = \frac{4}{7}$

La distribution invariante est $π = (\frac{4}{7}, \frac{3}{7})$ : on retrouve la limite $\frac{4}{7} \approx 57, 1 %$ obtenue par les suites.

4.6 Méthodes Clés

Méthode : Étudier une chaîne de Markov à deux états

Modéliser : identifier les états, dessiner le graphe orienté pondéré, écrire la matrice de transition $P$ (somme de chaque ligne $= 1$ ).
Distribution initiale $π_{0}$ , puis $π_{n} = π_{0} P^{n}$ (ou relation de récurrence $π_{n + 1} = π_{n} P$ , qui redonne une suite arithmético-géométrique sur la première composante).
Régime permanent : résoudre $π P = π$ avec $π = (a, 1 - a)$ pour obtenir la distribution invariante.

4.7 Algorithmique et Programmation


def produit(A, B):
    # Produit de deux matrices (listes de listes)
    n, p, q = len(A), len(B), len(B[0])
    C = [[0] * q for _ in range(n)]
    for i in range(n):
        for j in range(q):
            for k in range(p):
                C[i][j] = C[i][j] + A[i][k] * B[k][j]
    return C

def puissance(A, n):
    # Puissance n-ieme d'une matrice carree
    R = [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]
    for _ in range(n):
        R = produit(R, A)
    return R

# P = [[0.85, 0.15], [0.20, 0.80]]
# puissance(P, 20) : les deux lignes convergent vers (4/7, 3/7)

Produit et puissance de matrices (sans bibliothèque)

Continuer sur Adloun : animation, QCM, fiches, exercices