Maths expertes — Graphes
Graphes : problèmes d'optimisation
Coloration de graphes, plus court chemin (Dijkstra), arbre couvrant minimal, flots et applications
Résumé synthétiqueFiche en 5 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Une fois le vocabulaire posé, les graphes deviennent une machine à **optimiser**. Comment colorier une carte avec le moins de couleurs (le **nombre chromatique**) ? Comment trouver l'itinéraire le plus rapide entre deux villes (algorithme de **Dijkstra**) ? Comment câbler un réseau au moindre coût (**arbre couvrant minimal**, via Kruskal ou Prim) ? Comment maximiser le débit dans un réseau (**flot maximal**) ? Ces questions, qui semblent concrètes, cachent des algorithmes élégants et des résultats célèbres comme le **théorème des quatre couleurs** (toute carte se colorie avec $4$ couleurs) ou le théorème **flot max = coupe min**. Certains problèmes, comme le **voyageur de commerce**, restent à ce jour sans solution rapide connue : c'est tout l'enjeu de la complexité algorithmique.
Colorier un graphe, c'est attribuer une couleur à chaque sommet sans que deux voisins partagent la même. Le minimum de couleurs nécessaire, le **nombre chromatique**, modélise quantité de problèmes d'incompatibilité (emplois du temps, fréquences).
- Une **coloration** attribue une couleur à chaque sommet, deux sommets adjacents ayant des couleurs **différentes**.
- Le **nombre chromatique** $\chi(G)$ est le nombre minimal de couleurs nécessaires.
- $\chi(K_n) = n$ : dans un graphe complet, tous les sommets sont adjacents.
- **Théorème des quatre couleurs :** tout graphe **planaire** vérifie $\chi(G) \leq 4$.
- **Algorithme glouton :** colorier les sommets un par un avec la plus petite couleur disponible.
- **Applications :** emplois du temps (sommets = épreuves, arêtes = conflits), attribution de fréquences.
Exemple
Pour planifier des examens, on relie deux matières par une arête si un même élève les passe. Le nombre chromatique donne le nombre minimal de créneaux : deux matières adjacentes (en conflit) reçoivent des créneaux (couleurs) différents.
Piège à éviter
Le théorème des quatre couleurs ne concerne que les graphes **planaires** (dessinables sans croisement d'arêtes). Un graphe quelconque peut exiger bien plus de $4$ couleurs : $K_5$ en demande $5$.
Dans un **graphe pondéré**, chaque arête porte un poids (distance, coût, durée). Le problème vedette : trouver le chemin de poids total minimal entre deux sommets — la base de tout GPS.
- Un graphe **pondéré** attribue un poids à chaque arête (distance, coût, temps).
- Le **poids d'un chemin** est la somme des poids de ses arêtes.
- **Plus court chemin :** trouver le chemin de poids minimal entre deux sommets.
- L'**algorithme de Dijkstra** explore les sommets par distance croissante depuis la source.
- Dijkstra fonctionne tant que les poids sont **positifs ou nuls**.
Exemple
Dans le graphe ci-contre, le trajet direct $A \to B \to E$ coûte $5 + 2 = 7$, alors que le détour $A \to D \to E$ ne coûte que $2 + 4 = 6$. Le plus court chemin est donc $A \to D \to E$, de poids $6$.
Piège à éviter
Dijkstra suppose des poids **positifs ou nuls**. Avec un poids négatif, l'algorithme peut se tromper : il faut alors d'autres méthodes (comme Bellman-Ford).
Dijkstra construit les distances minimales pas à pas. À chaque étape, il « fige » le sommet non visité le plus proche, puis met à jour les distances de ses voisins : un raisonnement glouton qui se révèle optimal.
- **Initialisation :** distance de la source $= 0$, tous les autres sommets à $+\infty$.
- À chaque étape, on **sélectionne** le sommet non visité de distance minimale.
- Pour chaque voisin $v$ du sommet choisi $u$ : si $d(u) + \text{poids}(u\,;v) < d(v)$, on met à jour $d(v)$.
- On **marque** $u$ comme visité, puis on répète jusqu'à traiter tous les sommets.
- On reconstruit le chemin en **remontant** les prédécesseurs depuis l'arrivée.
Exemple
Source $A$, voisins $B$ (poids $5$) et $D$ (poids $2$). On fige $D$ (distance $2$, la plus petite). Depuis $D$, on atteint $E$ : $d(E) = 2 + 4 = 6$. Depuis $B$ on aurait $d(E) = 5 + 2 = 7 > 6$ : la valeur $6$ est conservée.
Piège à éviter
À chaque étape, on choisit le sommet non visité de distance **minimale**, pas le sommet de plus grand degré ni un sommet au hasard. C'est ce choix glouton qui garantit l'optimalité.
Pour relier tous les sommets au coût total le plus bas (sans boucle inutile), on cherche un **arbre couvrant minimal**. Deux algorithmes gloutons le construisent : Kruskal (par arêtes) et Prim (par sommets).
- Un **arbre couvrant** d'un graphe connexe contient tous les sommets et est un arbre ($n - 1$ arêtes).
- L'**arbre couvrant minimal** (ACM) minimise la **somme des poids** des arêtes retenues.
- **Kruskal :** trier les arêtes par poids croissant, ajouter chacune si elle ne crée pas de cycle.
- **Prim :** partir d'un sommet, ajouter à chaque étape l'arête de poids minimal reliant la zone déjà construite à un nouveau sommet.
- **Applications :** réseau câblé au moindre coût, réseau électrique minimal.
Exemple
Pour câbler $5$ villes au moindre coût, Kruskal trie toutes les liaisons possibles par prix croissant et les ajoute une à une, en sautant celles qui formeraient une boucle, jusqu'à obtenir $4$ liaisons ($n - 1$) connectant tout le monde.
Piège à éviter
L'arbre couvrant **minimal** (somme des poids la plus faible) n'a rien à voir avec le **plus court chemin** entre deux sommets : il relie **tous** les sommets, sans privilégier une paire.
Le monde des graphes regorge de problèmes célèbres, certains faciles, d'autres redoutables. Connaître leurs énoncés et leurs critères d'existence fait partie de la culture mathématique du chapitre.
- **Chemin eulérien :** passe par chaque arête exactement une fois. Existe (graphe connexe) si $0$ ou $2$ sommets sont de degré impair.
- **Cycle hamiltonien :** passe par chaque sommet exactement une fois (problème difficile).
- **Voyageur de commerce :** trouver le cycle hamiltonien de poids minimal (NP-difficile).
- **Flot maximal :** maximiser le débit de la source au puits ; théorème **flot max = coupe min**.
- **Applications :** logistique, réseaux de transport, ordonnancement de tâches.
Exemple
Les sept ponts de Königsberg : peut-on faire une promenade passant une seule fois par chaque pont ? Euler répond non, car plus de deux carrefours ont un degré impair — le critère du chemin eulérien n'est pas satisfait.
Piège à éviter
Ne confonds pas **eulérien** (toutes les **arêtes**, critère simple sur les degrés) et **hamiltonien** (tous les **sommets**, problème difficile sans critère simple). Les deux se ressemblent mais n'ont pas la même difficulté.
Quiz - Graphes : problèmes d'optimisation
10 questions
Articles utiles
Questions fréquentes
Les points clés à retenir sur Graphes : problèmes d'optimisation, extraits du quiz de révision.
Le nombre chromatique du graphe complet $K_4$ est :
Réponse :
$4$
Dans $K_4$, chaque sommet est adjacent à tous les autres : il faut une couleur par sommet, donc $\chi(K_4) = 4$.
Le théorème des quatre couleurs affirme que :
Réponse :
Tout graphe planaire est coloriable avec au plus $4$ couleurs
Le théorème ne s'applique qu'aux graphes **planaires** (dessinables dans le plan sans croisement d'arêtes).
L'algorithme de Dijkstra trouve :
Réponse :
Le plus court chemin depuis un sommet source
Dijkstra calcule le plus court chemin (en poids) depuis une source vers les autres sommets.
L'algorithme de Dijkstra exige que les poids soient :
Réponse :
Positifs ou nuls
Dijkstra ne fonctionne correctement que si tous les poids des arêtes sont positifs ou nuls.