Théorie des Graphes : Compréhension
Profonde
Décryptage du cours MTH1423 [cite : 3]
Introduction : Pourquoi les Graphes ?
Un graphe n’est rien d’autre qu’un modèle mathématique conçu pour représenter des
réseaux[cite : 21]. Qu’il s’agisse de personnes sur un réseau social ou d’un réseau de
plateformes logistiques interconnectées, le graphe fait abstraction de la géométrie pure
pour se concentrer sur une seule chose : les relations entre les éléments.
1 L’Anatomie d’un Graphe (Définitions Fondamentales)
Un graphe non orienté est défini formellement comme un couple G = (X, E)[cite : 39].
— L’ensemble X (Les sommets) : Ce sont les "points" de ton réseau[cite : 40]. Le
nombre total de sommets s’appelle l’ordre du graphe[cite : 41].
— L’ensemble E (Les arêtes) : Ce sont les liaisons physiques ou logiques entre ces
points. Le nombre total d’arêtes s’appelle la taille du graphe[cite : 41].
Nuances importantes de la terminologie [cite : 45]
— Adjacence vs Incidence : Deux sommets reliés par une arête sont dits adjacents
(ou voisins)[cite : 54]. L’arête elle-même est dite incidente à ces deux sommets[cite :
55].
— Boucles et Arêtes multiples : Si une arête relie un sommet à lui-même, c’est
une boucle[cite : 52]. Si plusieurs routes relient les deux mêmes entrepôts, ce sont
des arêtes parallèles[cite : 59]. Un graphe contenant cela est un multigraphe[cite :
60].
— Graphe Simple : C’est la forme la plus pure. Aucune boucle, et au maximum
une seule arête entre deux sommets[cite : 61]. Dans la réalité, cela correspond à
vérifier s’il existe (oui ou non) une connexion directe entre le point A et le point
B[cite : 62].
2 L’Isomorphisme : Le paradoxe de l’apparence
C’est un concept crucial. Visuellement, on peut dessiner un graphe de mille manières
différentes (en courbant les lignes, en déplaçant les points)[cite : 43, 44]. Deux graphes
sont isomorphes s’ils possèdent exactement la même structure de connexions,
indépendamment de leur dessin[cite : 94].
Mathématiquement, cela implique de trouver des bijections (des correspondances exactes
un-à-un) entre les sommets et les arêtes des deux graphes, de sorte que si deux sommets
1
sont reliés dans le premier graphe, leurs correspondants le soient obligatoirement dans le
second[cite : 93].
3 L’art du découpage : Les Sous-graphes
En ingénierie, on étudie rarement un réseau mondial d’un seul coup. On isole des
régions ou des sous-systèmes. C’est le rôle des sous-graphes[cite : 121].
1. Le Sous-graphe (standard) [cite : 124]
Tu choisis quelques sommets, et tu choisis certaines arêtes qui les relient.
2. Le Sous-graphe engendré (ou induit) [cite : 125]
Tu choisis une sélection de sommets, et la règle t’oblige à prendre absolument
toutes les arêtes qui existaient entre eux dans le graphe d’origine. C’est comme faire
un "zoom" sur une zone sans modifier son infrastructure locale.
3. Le Graphe partiel (ou couvrant) [cite : 126]
Tu gardes tous les sommets de ton réseau (Y = X), mais tu supprimes certaines
arêtes. C’est l’outil parfait pour modéliser une panne de réseau : tous les sites existent
encore, mais certaines routes sont coupées.
4 Degrés : Mesurer l’importance d’un "Nœud"
Le degré d’un sommet x, noté d(x), est le nombre de connexions directes qu’il possède
(nombre d’arêtes incidentes)[cite : 180]. Attention : Une boucle compte double (car elle
part du sommet et y revient, touchant le sommet deux fois)[cite : 181].
Si un graphe a tous ses sommets avec le même degré k, on dit qu’il est k-régulier[cite :
193]. (Un réseau logistique parfaitement équilibré).
Le joyau théorique : Le Lemme des poignées de main [cite : 185]
La proposition 1.1 énonce que :
X
d(x) = 2|E|
x∈X
Le sens caché : Si tu fais la somme de tous les degrés de tous les sommets, tu trouves
exactement le double du nombre total d’arêtes[cite : 188]. Pourquoi ? Parce que chaque
arête physique est un pont entre deux sommets. Quand tu comptes les degrés, tu parcours
chaque pont exactement deux fois (une fois depuis la rive gauche, une fois depuis la rive
droite).
La conséquence logique : Le Corollaire 1.1 [cite : 187]
"Dans un graphe, le nombre de sommets de degrés impairs est pair." [cite :
189]
C’est une obligation mathématique dictée par le lemme précédent. Puisque la somme
totale des degrés est toujours un nombre pair (2|E|), si tu as des sommets avec des degrés
impairs (comme 3 ou 5), tu es obligé d’en avoir un nombre pair (par exemple 2, 4 ou 6
sommets) pour que leur somme s’équilibre et donne un total pair.