Cours — Graphes (Maths Expertes)
Sommets • arêtes • chemins • graphes orientés • matrices d’adjacence • applications
0) Définition d’un graphe
Un graphe est un objet mathématique composé :
- d’un ensemble de sommets
- d’un ensemble de liens
\[
G = (S, A)
\]
- \(S\) : ensemble des sommets
- \(A\) : ensemble des arêtes (ou arcs)
1) Graphes non orientés
Dans un graphe non orienté, une arête relie deux sommets sans sens :
\[
\{A,B\} = \{B,A\}
\]
- On parle d’arête
- La relation est symétrique
⚠️ Attention : deux sommets peuvent être reliés par au plus une arête (dans le cadre du programme).
2) Graphes orientés
Dans un graphe orienté, chaque lien a un sens.
\[
(A,B) \neq (B,A)
\]
- On parle d’arc
- Le sens est représenté par une flèche
💡 Très utilisé pour modéliser :
- des déplacements
- des dépendances
- des processus (états → transitions)
3) Degré d’un sommet
Le degré d’un sommet est le nombre de liens qui lui sont incident.
- Graphe non orienté : nombre d’arêtes
- Graphe orienté :
- degré entrant
- degré sortant
⚠️ Somme des degrés (non orienté) = \(2 \times\) nombre d’arêtes.
4) Chemins et circuits
- Chemin : suite de sommets reliés successivement
- Longueur : nombre d’arêtes (ou arcs)
- Circuit : chemin fermé (départ = arrivée)
\[
A \rightarrow B \rightarrow C \rightarrow D
\]
💡 Les chemins servent à étudier :
- l’accessibilité
- les parcours possibles
- les transitions d’états
5) Matrice d’adjacence
À un graphe à \(n\) sommets, on associe une matrice carrée
\(A = (a_{ij})\).
\[
a_{ij} =
\begin{cases}
1 & \text{si il existe un arc de } i \text{ vers } j \\
0 & \text{sinon}
\end{cases}
\]
- Matrice souvent non symétrique
- Représentation algébrique du graphe
6) Puissances de la matrice d’adjacence
Pour \(k \in \mathbb{N}^*\), le coefficient \((A^k)_{ij}\) donne :
\[
\text{le nombre de chemins de longueur } k \text{ de } i \text{ à } j
\]
💡 Lien fondamental entre :
- algèbre linéaire
- graphes
- processus discrets
7) Applications classiques
- réseaux (routes, transport)
- chaînes de Markov
- processus de transitions
- informatique et algorithmique
🎯 Objectif Bac + Maths Expertes :
traduire une situation concrète en graphe puis en matrice.