Fiche — Graphes (Maths Expertes)
L’essentiel Bac : matrices d’adjacence • chemins • méthodes rapides • pièges classiques
1) Définitions essentielles
\[
G=(S,A)
\]
- Sommets : éléments de \(S\)
- Arêtes (non orienté) : \(\{i,j\}\)
- Arcs (orienté) : \((i,j)\)
- Chemin : suite de sommets reliés
- Longueur : nombre d’arêtes / arcs
- Circuit : chemin fermé
2) Degrés
- Non orienté : degré = nombre d’arêtes incidentes
- Orienté :
- degré entrant
- degré sortant
⚠️ Graphe non orienté :
\[
\sum \text{degrés} = 2 \times \text{nombre d’arêtes}
\]
3) Matrice d’adjacence — formules
\[
A=(a_{ij}) \quad\text{avec}\quad
a_{ij}=
\begin{cases}
1 & \text{si arc de } i \text{ vers } j \\
0 & \text{sinon}
\end{cases}
\]
- Taille : \(n \times n\)
- Non orienté → matrice symétrique
- Orienté → matrice en général non symétrique
4) Puissances de la matrice (résultat clé)
\[
(A^k)_{ij}
= \text{nombre de chemins de longueur } k
\text{ de } i \text{ à } j
\]
💡 Point central Maths Expertes :
les puissances comptent les chemins.
5) Méthodes types Bac
Méthode 1 — Construire la matrice
- Numéroter les sommets
- Lire ligne = départ, colonne = arrivée
- Placer 1 s’il existe un arc
Méthode 2 — Compter des chemins
- Calculer \(A^k\)
- Lire le coefficient demandé
Méthode 3 — Interprétation
- Coefficient nul → aucun chemin
- Coefficient positif → nombre de possibilités
6) Pièges classiques Bac
- ❌ Confondre ligne et colonne
- ❌ Oublier l’orientation des arcs
- ❌ Penser que \(A^2\) donne des chemins de longueur 1
- ❌ Compter les sommets au lieu des arêtes
- ❌ Croire que matrice toujours symétrique
⚠️ Toujours vérifier :
orientation → symétrie → longueur demandée.
7) Applications à connaître
- réseaux (transport, web)
- chaînes de Markov
- processus d’états
- algorithmique & informatique
🎯 Bac Maths Expertes :
graphe ⇄ matrice ⇄ interprétation concrète.