📄 Mémento Maths Expertes

🕸️ Graphes & matrices

Tout le chapitre sur une page : formules, méthode, pièges. À lire 5 min avant un contrôle.

📐Formules clés

Matrice d'adjacence

$M_{ij} = # {ar \overset{e}{ˆ} tes de i vers j}$

Ex : Triangle complet :

M = 011101110

Nombre de chemins

$(M^{n})_{ij} = # {chemins de longueur n}$

Ex :

(M^{2})_{ij}

compte les chemins de

i

j

2

étapes.

Degré d'un sommet

$d (i) = j \sum M_{ij}$

Ex : Somme des coefficients de la ligne

i

M

Lemme des poignées de main

$i \sum d (i) = 2 \times (nb d’ar \overset{e}{ˆ} tes)$

Ex :

4

sommets de degré

3

donnent

\frac{12}{2} = 6

arêtes.

Matrice de transition

$j \sum P_{ij} = 1, P_{ij} ⩾ 0$

Ex : Chaque ligne d'une chaîne de Markov somme à

1

Évolution d'un état

$π_{n + 1} = π_{n} P \Rightarrow π_{n} = π_{0} P^{n}$

Ex :

π_{n}

est un vecteur ligne de probabilités.

État stable

$π P = π, \sum π_{i} = 1$

Ex : L'état stable est le vecteur propre de

P

pour la valeur

1

⚠️Pièges à éviter

L'ordre $π_{n} P$ (vecteur ligne $\times$ matrice) compte : écrire $P π_{n}$ inverse les rôles et fausse tout.
Pour un graphe orienté, $M$ n'est pas symétrique : $M_{ij}$ et $M_{j i}$ peuvent différer.
Cherche l'état stable en résolvant $π P = π$ avec $\sum π_{i} = 1$ , pas en calculant une limite à la main.

💡

À retenir

Une question de graphe se traduit presque toujours en calcul matriciel : comptage de chemins via $M^n$, évolution via $P^n$ et état limite via $\pi P=\pi$.

🎯

Maintenant, entraîne-toi

Des exercices corrigés sur ce chapitre t'attendent

→

Autres mémentos — Maths Expertes

✨Nombres complexes 🔢Arithmétique 🟪Matrices