↩ Chapitre : Graphes et chaînes de Markov (ECG1-ECG2)
L’essentiel du chapitre Théorie des graphes du programme officiel d’ECG, option mathématiques appliquées, 1re année. Un graphe modélise un réseau (réseau social, web, échanges économiques), et le calcul matriciel permet de l’analyser.
1. Vocabulaire
Définitions
- Un graphe est formé de sommets reliés par des arêtes ; il est orienté si les arêtes ont un sens (on parle alors d’arcs).
- Deux sommets reliés par une arête sont adjacents.
- Une chaîne (un chemin dans un graphe orienté) est une suite de sommets consécutivement adjacents ; sa longueur est son nombre d’arêtes.
- Le degré d’un sommet est le nombre d’arêtes qui en partent.
- Un graphe est connexe si deux sommets quelconques sont toujours reliés par une chaîne.
2. Matrice d’adjacence
- Pour un graphe à
sommets, la matrice d’adjacence
a pour coefficient
s’il y a une arête de
vers
, et
sinon. - La matrice d’adjacence d’un graphe non orienté est symétrique.
Les deux résultats clés
- Nombre de chemins : le coefficient
de
est le nombre de chemins de longueur
allant du sommet
au sommet
. - Connexité : un graphe à
sommets est connexe si et seulement si la matrice
a tous ses coefficients strictement positifs.
Formule d’Euler (des poignées de main)
Dans un graphe non orienté, la somme des degrés des sommets est égale à deux fois le nombre d’arêtes : chaque arête est comptée deux fois, une fois par extrémité. En particulier, le nombre de sommets de degré impair est pair.
3. Exemples à connaître
- Graphe complet à
sommets : tous les sommets sont reliés deux à deux ; chaque sommet a pour degré
, et il y a
arêtes. - Graphe eulérien : on peut parcourir toutes les arêtes une et une seule fois en revenant au point de départ.
- Réseaux sociaux : le degré de centralité d’un sommet mesure son nombre de connexions (recherche d’« influenceurs ») ; ces mesures ne sont pas exigibles.
À savoir sur le programme
- Les mesures d’analyse des réseaux sociaux (centralité, intermédiarité) sont présentées sur des exemples mais ne sont pas exigibles.
- Les graphes probabilistes et chaînes de Markov sont étudiés en 2e année.
4. Pièges classiques
- Dans un graphe orienté, la matrice d’adjacence n’est en général pas symétrique : bien lire le sens des arcs.
compte les chemins de longueur exactement
; pour « au plus
», il faut sommer
.
En Python : construire la matrice d’adjacence avec numpy, calculer ses puissances avec np.linalg.matrix_power et compter les chemins.
Besoin d’aide sur ce chapitre ?
Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir ou un concours à préparer : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 20 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca, ou à distance, partout au Maroc et en France.
