Chapitre 1110 minIntermédiaire
Pour aller plus loin : graphes non orientés, Euler, coloration, arbres couvrants
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- calculer des degrés et appliquer le lemme des poignées de main ;
- reconnaître une chaîne eulérienne ;
- colorier un graphe avec l'algorithme glouton ;
- construire un arbre couvrant de poids minimal avec Kruskal.
4 exercices corrigés
Un graphe non orienté relie ses sommets par des arêtes, des liens sans sens de parcours : deux switchs reliés par un câble, deux points d'accès Wi-Fi qui se brouillent. Ce chapitre présente, hors du programme de l'E3, les notions classiques qui s'y rattachent : degré, chaîne, cycle et connexité, chaînes eulériennes, coloration, arbres et arbres couvrants de poids minimal. Elles apparaissent souvent dans les cours de théorie des graphes et dans les problèmes de réseau ; elles ne sont pas exigibles à l'examen, mais elles éclairent des situations que tu rencontreras en SISR comme en SLAM.
Arête, degré et lemme des poignées de main
Une arête {x, y} relie x et y sans orientation ; on dit que x et y sont voisins (ou adjacents). La matrice d'adjacence d'un graphe non orienté est symétrique : le coefficient (x, y) est égal au coefficient (y, x).
Le degré d'un sommet est le nombre d'arêtes qui le touchent (une boucle compte deux fois). Dans un réseau, c'est le nombre de câbles branchés sur un équipement.
Exemple : un réseau de 7 switchs peut-il être câblé pour que chacun soit relié à exactement 3 autres ? La somme des degrés vaudrait 7 × 3 = 21, un nombre impair, alors qu'elle doit être le double d'un entier : impossible.
Chaîne, cycle, connexité
Ce sont les équivalents non orientés des chemins et circuits :
- une chaîne est une suite de sommets dont chacun est voisin du suivant ;
- un cycle est une chaîne qui revient à son point de départ sans réutiliser d'arête ;
- un graphe est connexe si deux sommets quelconques sont toujours reliés par une chaîne : en réseau, toutes les machines peuvent communiquer.
Pour tester la connexité, on lance un parcours (en largeur ou en profondeur) depuis un sommet : le graphe est connexe si le parcours atteint tous les sommets. Ces parcours sont programmés dans le cours d'algorithmique.
Un graphe complet à n sommets, où chaque sommet est relié à tous les autres, a n(n − 1)/2 arêtes : c'est le nombre de liens d'un réseau maillé intégral, d'où son coût (45 liens pour 10 sites).
Chaînes et cycles eulériens
Une chaîne eulérienne passe une fois et une seule par chaque arête (et non par chaque sommet, comme un chemin hamiltonien). Le problème vient des sept ponts de Königsberg : en 1736, Leonhard Euler montra qu'on ne pouvait pas traverser chacun d'eux exactement une fois, acte de naissance de la théorie des graphes.
À Königsberg, les quatre zones de la ville avaient pour degrés 5, 3, 3 et 3 : quatre sommets impairs, pas de chaîne eulérienne. Application : la tournée d'un technicien qui doit inspecter chaque câble d'un réseau, ou d'un camion qui doit passer dans chaque rue, cherche une chaîne eulérienne.
Contraste à retenir : on sait décider très vite s'il existe une chaîne eulérienne (il suffit de compter les degrés), alors qu'aucune méthode rapide n'est connue pour les chemins hamiltoniens.
Coloration d'un graphe
Colorier un graphe, c'est donner une couleur à chaque sommet de sorte que deux sommets voisins n'aient jamais la même couleur. Le plus petit nombre de couleurs possible est le nombre chromatique. Si le graphe contient un triangle (trois sommets deux à deux voisins), il faut au moins 3 couleurs.
L'algorithme glouton de Welsh et Powell : range les sommets par degré décroissant ; donne la première couleur au premier sommet, puis à chaque sommet suivant de la liste qui n'est voisin d'aucun sommet déjà de cette couleur ; recommence avec une deuxième couleur pour les sommets restants, et ainsi de suite. Il ne garantit pas le minimum, mais donne souvent une bonne solution.
Exemple : les canaux Wi-Fi. Six points d'accès P1 à P6 ; deux points d'accès voisins (arête) se brouillent s'ils utilisent le même canal. Arêtes : P1–P2, P1–P3, P2–P3, P2–P4, P3–P5, P4–P5, P4–P6, P5–P6. En 2,4 GHz, on utilise couramment les trois canaux 1, 6 et 11, qui ne se chevauchent pas : peut-on s'en contenter ?
- Degrés : P1 : 2, P2 : 3, P3 : 3, P4 : 3, P5 : 3, P6 : 2. Ordre : P2, P3, P4, P5, P1, P6.
- Canal 1 : P2, puis P5 (non voisin de P2). P3, P4, P1 sont voisins de P2 ; P6 est voisin de P5.
- Canal 6 : P3, puis P4 (non voisin de P3). P1 est voisin de P3, P6 de P4.
- Canal 11 : P1 et P6, qui ne sont pas voisins.
Trois canaux suffisent : {P2, P5} sur le 1, {P3, P4} sur le 6, {P1, P6} sur le 11. Et il en faut au moins trois, à cause du triangle P1, P2, P3. La coloration sert aussi à bâtir un emploi du temps (deux examens qui ont des candidats communs ne peuvent pas avoir lieu en même temps) ou à allouer des registres dans un compilateur.
Arbres et arbre couvrant de poids minimal
Un arbre est un graphe non orienté connexe et sans cycle. Un arbre à n sommets a toujours n − 1 arêtes ; entre deux sommets, il existe une seule chaîne. C'est la version non orientée de l'arborescence du chapitre 5.
Dans un graphe connexe valué, un arbre couvrant de poids minimal relie tous les sommets avec des arêtes du graphe, sans cycle, pour un poids total minimal : c'est le câblage le moins cher qui relie tous les sites.
L'algorithme de Kruskal (1956) : range les arêtes par poids croissant ; prends-les une par une, en gardant chaque arête qui ne crée pas de cycle avec celles déjà retenues ; arrête-toi à n − 1 arêtes.
Exemple. Cinq bâtiments A à E ; coût de pose d'une fibre (en milliers d'euros) : AB 4, AC 3, BC 2, BD 5, CD 7, CE 6, DE 1.
| Arête (par poids croissant) | DE (1) | BC (2) | AC (3) | AB (4) | BD (5) |
|---|---|---|---|---|---|
| Décision | gardée | gardée | gardée | rejetée : cycle A, B, C | gardée : 4 arêtes, fin |
L'arbre couvrant minimal est {DE, BC, AC, BD}, de coût 1 + 2 + 3 + 5 = 11 000 €. L'algorithme de Prim obtient le même arbre en le faisant grandir à partir d'un sommet, en ajoutant à chaque étape l'arête la moins chère qui relie l'arbre à un nouveau sommet.
En réseau local, le protocole STP (Spanning Tree Protocol) des switchs construit un arbre couvrant du réseau pour supprimer les boucles de niveau 2 tout en gardant tous les switchs reliés ; son fonctionnement est détaillé dans le cours routage et commutation.
Les flots, en un mot
Un réseau de transport est un graphe orienté dont chaque arc a une capacité (un débit maximal). Chercher le flot maximal d'une source vers un puits, c'est calculer le plus grand débit qui peut traverser le réseau en respectant les capacités ; l'algorithme de Ford-Fulkerson (1956) le résout, et le théorème « flot maximal = coupe minimale » dit que ce débit est limité par le goulot d'étranglement le plus étroit. On l'utilise pour dimensionner des liaisons ou répartir une charge.
Exercices
Exercice 1 sur 4 Degrés et câblage Réussi À revoir
- Un graphe non orienté a 6 sommets de degrés 1, 2, 2, 3, 3, 5. Combien a-t-il d'arêtes ?
- Peut-on relier 5 serveurs de sorte que chacun soit relié à exactement 3 autres ? Et 6 serveurs ?
Voir la réponseMasquer la réponse de l'exercice 1
- Somme des degrés : 1 + 2 + 2 + 3 + 3 + 5 = 16 = 2 × 8. Le graphe a 8 arêtes.
- Avec 5 serveurs : 5 × 3 = 15, impair, impossible. Avec 6 serveurs : 6 × 3 = 18 = 2 × 9, possible, avec 9 liens : par exemple, deux triangles A, B, C et D, E, F, plus les liens A–D, B–E et C–F.
Tu avais trouvé ?
Exercice 2 sur 4 Chaîne eulérienne Réussi À revoir
Un graphe a pour sommets A, B, C, D, E et pour arêtes AB, AC, BC, BD, CD, CE, DE.
- Calcule le degré de chaque sommet.
- Le graphe a-t-il une chaîne eulérienne ? Si oui, donne-en une.
Voir la réponseMasquer la réponse de l'exercice 2
- A : 2, B : 3, C : 4, D : 3, E : 2 (somme 14 = 2 × 7 arêtes).
- Le graphe est connexe et a exactement 2 sommets de degré impair, B et D : il a une chaîne eulérienne, qui va de B à D. Par exemple B, A, C, B, D, C, E, D : elle utilise AB, AC, CB, BD, DC, CE, ED, chacune une fois.
Tu avais trouvé ?
Exercice 3 sur 4 Emploi du temps des examens Réussi À revoir
Cinq épreuves doivent être planifiées : mathématiques (M), CEJM (C), anglais (A), réseaux (R), développement (D). Deux épreuves ont des candidats communs (et ne peuvent donc pas avoir lieu sur le même créneau) dans les cas suivants : M et C, M et A, C et A, A et R, R et D, D et M.
- Représente la situation par un graphe et applique l'algorithme de Welsh et Powell.
- Combien de créneaux faut-il au minimum ?
Voir la réponseMasquer la réponse de l'exercice 3
- Degrés : M : 3, A : 3, C : 2, R : 2, D : 2. Ordre : M, A, C, R, D. Créneau 1 : M, puis R (non voisin de M) ; A et C sont voisins de M, D aussi. Créneau 2 : A, puis D (non voisin de A) ; C est voisin de A. Créneau 3 : C. Résultat : {M, R}, {A, D}, {C}.
- M, C et A sont deux à deux en conflit (un triangle) : il faut au moins 3 créneaux, et la solution trouvée en utilise 3. 3 créneaux au minimum.
Tu avais trouvé ?
Exercice 4 sur 4 Câblage au moindre coût Réussi À revoir
Six sites P, Q, R, S, T, U ; coûts de liaison possibles (en k€) : PQ 6, PR 3, QR 4, QS 2, RS 5, RT 7, ST 8, SU 9, TU 1.
Applique l'algorithme de Kruskal et donne le coût du réseau le moins cher qui relie les six sites.
Voir la réponseMasquer la réponse de l'exercice 4
Arêtes par poids croissant : TU (1) gardée ; QS (2) gardée ; PR (3) gardée ; QR (4) gardée (relie {P, R} et {Q, S}) ; RS (5) rejetée (cycle Q, R, S) ; PQ (6) rejetée (cycle P, Q, R) ; RT (7) gardée (relie {T, U} au reste) : on a 5 arêtes pour 6 sommets, fin. Arbre : {TU, QS, PR, QR, RT}, coût 1 + 2 + 3 + 4 + 7 = 17 k€.
Tu avais trouvé ?