Ascension Maths

I. Vocabulaire des graphes

Un graphe représente des objets et les liens qui les unissent : des villes et des routes, des pages et des liens, des états et des transitions. Le vocabulaire est court, et il suffit à poser la plupart des problèmes.

DéfinitionDéfinitions

Un graphe est constitué de sommets et d'arêtes reliant certains couples de sommets.

Deux sommets reliés par une arête sont dits adjacents. Le degré d'un sommet est le nombre d'arêtes qui en partent. L'ordre du graphe est son nombre de sommets.

Une chaîne est une suite d'arêtes consécutives ; sa longueur est le nombre d'arêtes qui la composent. Un graphe est connexe lorsque deux sommets quelconques sont toujours reliés par une chaîne.

Un graphe complet est un graphe dans lequel tous les sommets sont deux à deux adjacents.

DéfinitionMatrice d'adjacence

On numérote les sommets d'un graphe d'ordre $n$ . Sa matrice d'adjacence est la matrice carrée $A$ de taille $n$ dont le coefficient situé ligne $i$ et colonne $j$ vaut $1$ si les sommets $i$ et $j$ sont reliés, et $0$ sinon.

Pour un graphe non orienté, cette matrice est symétrique.

II. Calcul matriciel

DéfinitionMatrices et opérations

Une matrice est un tableau de nombres réels. Une matrice carrée a autant de lignes que de colonnes ; une matrice ligne n'a qu'une ligne, une matrice colonne qu'une colonne.

L'addition et la multiplication par un réel se font coefficient par coefficient.

Le produit $AB$ n'est défini que si le nombre de colonnes de $A$ égale le nombre de lignes de $B$ . Le coefficient situé ligne $i$ et colonne $j$ du produit s'obtient en multipliant terme à terme la ligne $i$ de $A$ par la colonne $j$ de $B$ , puis en additionnant.

Attention

Le produit de matrices n'est pas commutatif : les produits $AB$ et $BA$ diffèrent en général, et l'un peut exister sans l'autre. L'ordre des facteurs doit donc être respecté scrupuleusement.

DéfinitionInverse et puissances

La matrice identité $I$ possède des $1$ sur sa diagonale et des $0$ ailleurs ; elle joue le rôle du nombre $1$ .

Une matrice carrée $A$ est inversible s'il existe une matrice $A^{-1}$ telle que $AA^{-1}=A^{-1}A=I$ .

Les puissances se définissent par $A^0 = I$ et $A^{n+1}=A^n \times A$ .

ExempleRésoudre un système

Un système linéaire s'écrit matriciellement $AX=B$ , où $X$ est la colonne des inconnues.

Si $A$ est inversible, la solution s'obtient par

X = A^{-1}B

La calculatrice fournit l'inverse, ce qui rend la résolution immédiate pour un système de trois équations à trois inconnues.

III. Compter les chemins

ThéorèmePuissances de la matrice d'adjacence

Soit $A$ la matrice d'adjacence d'un graphe. Pour tout entier naturel $n$ non nul, le coefficient situé ligne $i$ et colonne $j$ de $A^n$ est le nombre de chaînes de longueur $n$ reliant le sommet $i$ au sommet $j$ .

Démonstration : Nombre de chemins de longueur

n

Raisonnons par récurrence sur $n$ .

Pour $n=1$ , le coefficient de $A$ vaut $1$ s'il existe une arête entre $i$ et $j$ , et $0$ sinon : c'est bien le nombre de chaînes de longueur $1$ .

Supposons la propriété vraie au rang $n$ . Une chaîne de longueur $n+1$ allant de $i$ à $j$ se décompose de façon unique en une chaîne de longueur $n$ allant de $i$ à un sommet intermédiaire $k$ , suivie d'une arête de $k$ à $j$ .

En sommant sur tous les sommets intermédiaires possibles, le nombre de telles chaînes vaut

\sum_{k} \big(A^n\big)_{i,k} \times A_{k,j}

Or cette somme est exactement le coefficient situé ligne $i$ et colonne $j$ du produit $A^n \times A$ , c'est-à-dire de $A^{n+1}$ .

La propriété est donc héréditaire, ce qui achève la démonstration.

Exemple

Dans un réseau de quatre villes, le coefficient ligne $1$ colonne $3$ de $A^2$ donne le nombre d'itinéraires reliant la ville $1$ à la ville $3$ en exactement deux étapes.

Un coefficient nul signale qu'aucun trajet de cette longueur n'existe, ce qui ne veut pas dire que les villes ne sont pas reliées : un trajet plus long peut exister.

IV. Chaînes de Markov

Une chaîne de Markov décrit un système qui passe d'un état à un autre au hasard, la probabilité de la prochaine transition ne dépendant que de l'état actuel. Le programme se limite à deux ou trois états.

DéfinitionDistribution et matrice de transition

La distribution à l'étape $n$ est la matrice ligne $\pi_n$ dont les coefficients sont les probabilités de se trouver dans chacun des états. Leur somme vaut $1$ .

La matrice de transition $P$ a pour coefficient ligne $i$ colonne $j$ la probabilité de passer de l'état $i$ à l'état $j$ en une étape. Chaque ligne de $P$ a pour somme $1$ .

Le graphe orienté pondéré associé porte ces probabilités sur ses flèches.

ThéorèmeÉvolution de la distribution

Pour tout entier naturel $n$ :

\pi_{n+1}=\pi_n P \qquad \text{et donc} \qquad \pi_n = \pi_0 P^n

De plus, le coefficient ligne $i$ colonne $j$ de $P^n$ est la probabilité de passer de l'état $i$ à l'état $j$ en $n$ transitions.

Démonstration : Distribution après

n

transitions

La formule des probabilités totales, appliquée à la partition formée par les états possibles à l'étape $n$ , donne pour chaque état $j$ :

P(\text{état } j \text{ à l'étape } n+1)=\sum_{i} P(\text{état } i \text{ à l'étape } n) \times P_{i,j}

Le membre de droite est exactement le coefficient $j$ du produit de la matrice ligne $\pi_n$ par la matrice $P$ . Donc $\pi_{n+1}=\pi_n P$ .

Une récurrence immédiate donne alors $\pi_n = \pi_0 P^n$ .

DéfinitionDistribution invariante

Une distribution $\pi$ est invariante lorsqu'elle vérifie

\pi P = \pi

Une fois atteinte, elle ne change plus : le système est en régime stationnaire.

MéthodeDéterminer la distribution invariante

On pose $\pi = \begin{pmatrix} x & y \end{pmatrix}$ pour deux états, puis on résout le système donné par $\pi P = \pi$ , complété par la condition $x+y=1$ .

Cette dernière équation est indispensable : sans elle, le système admet une infinité de solutions proportionnelles, et une seule est une distribution de probabilité.

Exemple

Un abonné change d'opérateur d'une année sur l'autre selon la matrice

P = \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}2 & 0{,}8 \end{pmatrix}

La distribution invariante $\begin{pmatrix} x & y \end{pmatrix}$ vérifie $0{,}9x+0{,}2y=x$ et $x+y=1$ .

La première équation donne $0{,}2y=0{,}1x$ , donc $x=2y$ . Avec $x+y=1$ , on obtient

x=\frac{2}{3} \qquad y=\frac{1}{3}

À long terme, deux tiers des abonnés se trouvent chez le premier opérateur, quelle que soit la répartition de départ.

Passer à la pratique

9 exercices corrigés sur ce chapitre.

Graphes et matrices

Avant de commencer

À la fin du chapitre, tu sais

I. Vocabulaire des graphes

II. Calcul matriciel

III. Compter les chemins

IV. Chaînes de Markov