Introduction à la théorie des graphes : du vocabulaire
Mathématiques Expertes · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Définitions et théorèmes
Un graphe G est constitué d'un ensemble de sommets et d'un ensemble d'arêtes reliant certains couples de sommets. Vocabulaire :
Ordre : nombre de sommets du graphe.
Sommets adjacents : reliés par une arête.
Degré d'un sommet : nombre d'arêtes qui lui sont incidentes (une boucle compte 2).
Chaîne : suite d'arêtes consécutives ; cycle : chaîne fermée.
Graphe connexe : tout couple de sommets est relié par une chaîne.
Graphe complet K_n : tous les sommets sont reliés deux à deux.
Graphe orienté : les liaisons sont des arcs (flèches) ; on distingue degré entrant et degré sortant.
Lemme des poignées de main. Dans tout graphe, la somme des degrés des sommets vaut le double du nombre d'arêtes :
\sum_{i} \deg(s_i)=2\times (\text{nombre d'arêtes}).
Conséquence : cette somme est toujours paire, et le nombre de sommets de degré impair est toujours pair.
Théorème d'Euler. Un graphe connexe admet une chaîne eulérienne (passant une seule fois par chaque arête) si et seulement s'il possède exactement 0 ou 2 sommets de degré impair. Il admet un cycle eulérien si et seulement si tous ses sommets ont un degré pair.
Formules
Nombre d'arêtes =\dfrac{1}{2}\displaystyle\sum_i \deg(s_i).
Dans K_n : chaque sommet a un degré n-1, le nombre d'arêtes vaut \dfrac{n(n-1)}{2}.
Méthodes type bac
Compter les arêtes : sommer les degrés et diviser par 2.
Décider de l'existence d'un graphe : une suite de degrés de somme impaire ne correspond à aucun graphe.
Chercher une chaîne/cycle eulérien : compter les sommets de degré impair et appliquer le théorème d'Euler.
Tester la connexité : vérifier qu'on peut atteindre tout sommet depuis un sommet donné.
Pièges
Une boucle ajoute 2 au degré, pas 1.
La somme des degrés est toujours paire : une suite de degrés de somme impaire est impossible.
Chaîne eulérienne (chaque arête une fois) à ne pas confondre avec chaîne hamiltonienne (chaque sommet une fois).
Connexe ne signifie pas complet : un graphe peut être connexe sans que tous les sommets soient reliés directement.
Pour l'épreuve
Le vocabulaire (ordre, degré, connexe, complet, eulérien) doit être parfaitement maîtrisé. Les questions classiques portent sur le lemme des poignées de main et le critère d'Euler pour les chaînes/cycles. Sache lire une liste d'arêtes, en déduire les degrés, et conclure rigoureusement. Pense à traduire un énoncé concret (réseau routier, planning, problème de coloration) en graphe : choisir ce que représentent les sommets et les arêtes est souvent la première étape valorisée. Enfin, garde en mémoire que ce vocabulaire prépare directement le chapitre suivant, où la matrice d'adjacence permettra de compter les chemins par le calcul matriciel.