Les graphes
Objectifs du Chapitre
Définir un graphe, ses sommets, ses arêtes, et distinguer orienté, pondéré, simple.
Calculer les degrés et appliquer le lemme des poignées de main.
Écrire une matrice d'adjacence et une liste d'adjacence, et passer de l'une à l'autre.
Interpréter les puissances de la matrice d'adjacence en nombre de chemins.
Reconnaître un graphe connexe, un cycle, un arbre, un graphe biparti.
Déterminer un plus court chemin par l'algorithme de Dijkstra.
Reconnaître l'existence d'un parcours eulérien, et encadrer le nombre chromatique.
Définitions
Un graphe G = (V, E) est la donnée d'un ensemble V de sommets (ou nœuds) et d'un ensemble E d'arêtes, chaque arête reliant deux sommets.
Ce qui compte, c'est uniquement la relation « est relié à ». La position des points sur le dessin, la longueur ou la courbure des traits n'ont aucune signification : deux dessins très différents peuvent représenter le même graphe.
Non orienté : la relation est réciproque, comme une amitié ou un câble.
Pondéré : chaque arête porte un nombre (distance, coût, durée).
Simple : ni boucle (arête d'un sommet vers lui-même), ni arête multiple entre deux mêmes sommets.
Le graphe de référence du chapitre
Tous les exemples qui suivent portent sur celui-ci, non orienté, à quatre sommets :
A ──── B
│ │
│ │
D ──── C
Arêtes : (A,B), (A,D), (B,C), (C,D). Quatre sommets, quatre arêtes.
Degrés
Le degré d'un sommet est le nombre d'arêtes qui y aboutissent (une boucle compte double). Dans un graphe orienté, on distingue le degré entrant et le degré sortant.
Dans le graphe de référence, chaque sommet est de degré 2.
La somme des degrés de tous les sommets vaut deux fois le nombre d'arêtes.
Σ deg(v) = 2 |E|
La démonstration tient en une phrase : chaque arête a deux extrémités, donc elle est comptée une fois dans le degré de chacune. Vérification sur l'exemple : 2 + 2 + 2 + 2 = 8 = 2 × 4 ✓
Représentations
Liste d'adjacence
À chaque sommet on associe la liste de ses voisins :
A : B, D
B : A, C
C : B, D
D : A, C
Économe en mémoire quand le graphe a peu d'arêtes, et pratique pour parcourir les voisins d'un sommet.
Matrice d'adjacence
La matrice d'adjacence M d'un graphe à n sommets est la matrice n × n dont le coefficient mᵢⱼ vaut 1 s'il existe une arête de i vers j, et 0 sinon. Pour un graphe pondéré, on y met le poids au lieu de 1.
Pour le graphe de référence, en rangeant les sommets dans l'ordre A, B, C, D :
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 0 | 1 |
| B | 1 | 0 | 1 | 0 |
| C | 0 | 1 | 0 | 1 |
| D | 1 | 0 | 1 | 0 |
Deux lectures immédiates : la matrice d'un graphe non orienté est symétrique, et la somme d'une ligne donne le degré du sommet correspondant.
Puissances de la matrice d'adjacence
C'est le point de rencontre entre ce chapitre et celui sur les matrices, et il tombe souvent en épreuve.
Le coefficient (i, j) de la matrice M^k est le nombre de chemins de longueur exactement k allant du sommet i au sommet j.
L'idée de la démonstration : le coefficient (i,j) de M² vaut Σ mᵢₖ mₖⱼ. Chaque terme de cette somme vaut 1 si et seulement s'il existe une arête de i vers k et une de k vers j, c'est-à-dire un chemin en deux étapes. La somme compte donc tous ces chemins.
Calculons M² sur l'exemple :
| A | B | C | D | |
|---|---|---|---|---|
| A | 2 | 0 | 2 | 0 |
| B | 0 | 2 | 0 | 2 |
| C | 2 | 0 | 2 | 0 |
| D | 0 | 2 | 0 | 2 |
Lecture : il y a 2 chemins de longueur 2 entre A et C (par B, et par D), ce qui se lit sur le dessin. Et 0 chemin de longueur 2 entre A et B : normal, il faudrait un nombre impair d'étapes. Ce zéro est d'ailleurs la signature d'un graphe biparti.
Chemins, cycles, connexité
Une chaîne est une suite de sommets consécutivement reliés. Sa longueur est son nombre d'arêtes. Un cycle est une chaîne fermée qui ne réutilise pas deux fois la même arête. Un graphe est connexe si toute paire de sommets est reliée par au moins une chaîne. Une composante connexe est un morceau connexe maximal.
La distance entre deux sommets est la longueur de la plus courte chaîne qui les relie (dans un graphe non pondéré).
Le graphe de référence est connexe, et contient un cycle : A → B → C → D → A, de longueur 4.
Arbres
Un arbre est un graphe connexe sans cycle.
Un arbre à n sommets a exactement n − 1 arêtes. Réciproquement, un graphe connexe à n − 1 arêtes est un arbre. Entre deux sommets d'un arbre, il existe exactement une chaîne.
C'est la structure la plus économique qui garde tout connecté : une arête de moins et le graphe se coupe en deux, une arête de plus et un cycle apparaît. C'est pour ça qu'un réseau qu'on veut connecter au moindre coût est toujours un arbre.
Graphes orientés sans cycle (DAG)
Un DAG (Directed Acyclic Graph) est un graphe orienté sans cycle. On ne peut jamais revenir en arrière en suivant les flèches. C'est la structure des dépendances : tâches d'un projet, prérequis d'un cursus, ordre de compilation. Un DAG admet toujours un tri topologique : un ordre des sommets tel que chaque flèche va de gauche à droite, autrement dit un planning valide.
Plus court chemin : l'algorithme de Dijkstra
Dans un graphe pondéré à poids positifs, on cherche le chemin de coût total minimal entre deux sommets. Dijkstra le trouve sans explorer toutes les possibilités.
On maintient pour chaque sommet une distance provisoire depuis le départ, initialisée à +∞ (sauf le départ, à 0). À chaque étape :
- choisir le sommet non traité de plus petite distance provisoire ;
- le marquer comme définitivement traité ;
- mettre à jour ses voisins : si passer par lui améliore leur distance, remplacer la valeur et noter le prédécesseur.
On s'arrête quand tous les sommets sont traités.
Exemple travaillé. Graphe pondéré : A–B (4), A–C (2), C–B (1), B–D (5), C–D (8).
| Étape | A | B | C | D | Traité |
|---|---|---|---|---|---|
| départ | 0 | ∞ | ∞ | ∞ | aucun |
| depuis A | 0 | 4 (par A) | 2 (par A) | ∞ | A |
| depuis C | 0 | 3 (par C) | 2 | 10 (par C) | C |
| depuis B | 0 | 3 | 2 | 8 (par B) | B |
Le chemin le plus court de A à D vaut 8, par A → C → B → D.
Parcours eulériens
Un parcours eulérien emprunte chaque arête exactement une fois. S'il revient à son point de départ, c'est un circuit eulérien.
C'est le problème des ponts de Königsberg, à l'origine de toute la théorie des graphes, et c'est aussi celui du facteur qui veut passer une seule fois dans chaque rue.
Un graphe connexe admet
- un circuit eulérien si et seulement si tous ses sommets sont de degré pair ;
- un parcours eulérien (départ et arrivée différents) si et seulement s'il a exactement deux sommets de degré impair, et le parcours doit alors partir de l'un et finir sur l'autre.
Dans tous les autres cas, il n'en existe pas.
Le critère est purement local : on compte les degrés, on conclut. C'est ce qui en fait une question d'examen idéale.
Sur le graphe de référence, tous les degrés valent 2 : il existe un circuit eulérien, A → B → C → D → A.
Coloration
Colorer un graphe, c'est attribuer une couleur à chaque sommet de sorte que deux sommets reliés n'aient jamais la même couleur. Le nombre chromatique γ(G) est le nombre minimal de couleurs nécessaires.
L'application classique : des examens qui ne doivent pas se chevaucher (deux épreuves reliées si un étudiant est inscrit aux deux), des fréquences radio à attribuer, des variables à ranger dans des registres.
Deux encadrements permettent de conclure sans chercher exhaustivement :
- Minorant : si le graphe contient une clique de taille k (k sommets tous reliés deux à deux), alors
γ ⩾ k. - Majorant (théorème de Welsh-Powell) :
γ ⩽ Δ + 1, où Δ est le degré maximal.
Sur la copie, on encadre puis on exhibe une coloration atteignant le minorant, ce qui prouve l'égalité.
Le graphe de référence est biparti (A, C d'un côté, B, D de l'autre) : deux couleurs suffisent, et il en faut au moins deux puisqu'il y a des arêtes. Donc γ = 2.
Un graphe est biparti si et seulement s'il ne contient aucun cycle de longueur impaire, ce qui équivaut à γ ⩽ 2.
Exercices type
1. Existe-t-il un graphe simple à 6 sommets dont les degrés sont 5, 5, 4, 3, 2, 1 ?
Somme des degrés : 5+5+4+3+2+1 = 20, ce qui est pair → il y aurait 10 arêtes. Le lemme des poignées de main ne l'interdit donc pas.
Mais regardons plus finement : deux sommets sont de degré 5, donc chacun est relié à tous les autres. Le sommet de degré 1 est alors relié à ces deux-là, ce qui lui fait un degré d'au moins 2. Contradiction : ce graphe n'existe pas.
La leçon : le lemme des poignées de main est une condition nécessaire, pas suffisante.
2. Un graphe a 8 sommets et 7 arêtes. Est-ce un arbre ?
Il a bien n − 1 = 7 arêtes, ce qui est la bonne quantité, mais seulement s'il est connexe.
S'il ne l'est pas, on peut par exemple avoir un cycle de 4 sommets d'un côté et un chemin de 4 sommets de l'autre : 4 + 3 = 7 arêtes, et ce n'est pas un arbre.
Conclusion : on ne peut pas répondre sans savoir s'il est connexe.
3. Que vaut le coefficient (A,A) de M³ dans le graphe de référence ?
C'est le nombre de chemins de longueur 3 de A vers A. Or A et C sont dans une classe, B et D dans l'autre (graphe biparti) : un chemin de longueur impaire change forcément de classe, donc il ne peut pas revenir en A.
Le coefficient vaut 0. Plus généralement, toutes les puissances impaires de M ont une diagonale nulle ici.
4. Un facteur peut-il parcourir chaque rue une seule fois et revenir au dépôt ?
C'est la question du circuit eulérien. Il faut et il suffit que le graphe soit connexe et que tous les carrefours soient de degré pair.
S'il y a exactement deux carrefours de degré impair, il peut faire la tournée sans repasser deux fois, mais il finira ailleurs qu'au dépôt (en partant de l'un des deux carrefours impairs).
S'il y en a quatre ou plus, c'est impossible sans repasser par certaines rues.
5. Nombre chromatique d'un cycle à 5 sommets
Un cycle de longueur impaire ne peut pas être biparti, donc γ ⩾ 3.
Et 3 couleurs suffisent : on alterne deux couleurs sur quatre sommets, et on donne la troisième au dernier.
γ = 3. (Pour un cycle de longueur paire, γ = 2.)
6. Plus court chemin de S à T : S–A (2), S–B (5), A–B (1), A–T (7), B–T (3)
Dijkstra depuis S :
- traité S : A à 2, B à 5
- traité A (le plus petit) : B passe de 5 à
2 + 1 = 3(par A), T à2 + 7 = 9 - traité B : T passe de 9 à
3 + 3 = 6(par B)
Distance 6, par S → A → B → T. Le chemin direct A→T, plus court en nombre d'arêtes, était plus coûteux : c'est tout l'intérêt de l'algorithme.
La méthode sur feuille
- Redessine le graphe proprement, quitte à déplacer les sommets pour éviter que les arêtes se croisent. La moitié des questions se lit sur un bon dessin.
- Calcule tous les degrés et vérifie le lemme des poignées de main : c'est un contrôle immédiat de ta lecture de l'énoncé.
- Pour une question de parcours eulérien, compte les sommets de degré impair : 0 → circuit, 2 → parcours, sinon impossible.
- Pour Dijkstra, fais un tableau avec une ligne par étape et note les prédécesseurs.
- Pour une coloration, encadre : clique pour le minorant,
Δ + 1pour le majorant, puis exhibe une coloration optimale. - Pour un nombre de chemins, pense aux puissances de la matrice d'adjacence.
En résumé
- Un graphe ne retient que « qui est relié à qui ». Le dessin n'a aucune importance.
- Lemme des poignées de main :
Σ deg = 2 |E|. Le nombre de sommets de degré impair est toujours pair. - Matrice d'adjacence : symétrique si le graphe est non orienté ; la somme d'une ligne donne le degré.
- Le coefficient (i,j) de
M^kest le nombre de chemins de longueur k de i à j. - Arbre = connexe et sans cycle ⟺ connexe avec
n − 1arêtes. Une seule chaîne entre deux sommets. - DAG = orienté sans cycle → modélise les dépendances, admet un tri topologique.
- Dijkstra : poids positifs, on fige à chaque étape le sommet non traité le plus proche, et on note les prédécesseurs.
- Euler : circuit ⟺ tous les degrés pairs ; parcours ⟺ exactement deux degrés impairs.
- Coloration :
clique ⩽ γ ⩽ Δ + 1.γ = 2⟺ biparti ⟺ aucun cycle impair.
Et ensuite ? Le chapitre Matrices et systèmes complète l'épreuve d'algèbre du semestre 2, et donne les outils de calcul sur les matrices d'adjacence que tu viens de croiser.