Recherche opérationnelle
Les graphes, vocabulaire et représentation
- Présentation du cours
- Qu'est-ce que la recherche opérationnelle
- Modéliser un problème de décision
- Le programme linéaire et ses formes
- La résolution graphique
- Le simplexe, la méthode
- Le simplexe, les cas particuliers
- La dualité
- L'analyse de sensibilité
- Le problème de transport
- Le problème d'affectation
- Les graphes, vocabulaire et représentation
- Le plus court chemin
- Le flot maximal
- L'ordonnancement de projet
- La programmation en nombres entiers
- Gestion des stocks et files d'attente
Recherche opérationnelle
Chapitre 10 : Les graphes, vocabulaire et représentation
Le vocabulaire
La définition
Un graphe
G = (X, U)
X est l’ensemble des sommets, U celui des arcs — des couples de sommets.
Orienté ou non
Si les couples sont ordonnés, le graphe est orienté : on parle d’arcs, et (i,j) diffère de (j,i).
Sinon il est non orienté : on parle d’arêtes.
Le choix n’est pas décoratif
Une route à sens unique, une relation hiérarchique, un ordre de fabrication : orienté.
Une ligne de chemin de fer, une frontière commune : non orienté.
Les notions de base
Cinq mots
Le degré d’un sommet est son nombre d’arcs. En orienté, on distingue demi-degré entrant et sortant.
Un chemin est une suite d’arcs consécutifs ; un circuit est un chemin qui revient à son origine.
Un graphe est connexe si tout sommet est joignable depuis tout autre.
Ce que ces mots servent à dire
Un sommet de demi-degré entrant nul est une source — une usine, une tâche initiale.
Un sommet de demi-degré sortant nul est un puits — un client, la fin du projet.
Le réseau de livraison
L’exemple
Six dépôts, huit liaisons
Un transporteur relie six dépôts A à F. Chaque arc porte une distance en kilomètres.
Les distances
Les huit arcs
| Arc | km | Arc | km | |
|---|---|---|---|---|
| A \to B | 4 | C \to E | 3 | |
| A \to C | 2 | E \to D | 4 | |
| B \to C | 5 | E \to F | 9 | |
| B \to D | 10 | D \to F | 11 |
La question qui suit
Quel est le trajet le plus court de A à F ?
À l’œil, on voit trois chemins possibles. Sur un réseau de deux mille sommets, l’œil ne voit plus rien : c’est là que l’algorithme devient nécessaire.
Représenter un graphe
La matrice d’adjacence
La définition
a_{ij} = \begin{cases} 1 & \text{s'il existe un arc de } i \text{ vers } j\\ 0 & \text{sinon}\end{cases}
Pour un graphe non orienté, la matrice est symétrique.
Sur notre réseau
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 | 0 | 0 |
| B | 0 | 0 | 1 | 1 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 1 | 0 |
| D | 0 | 0 | 0 | 0 | 0 | 1 |
| E | 0 | 0 | 0 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 0 | 0 | 0 |
Ce que ses puissances révèlent
Le résultat
Le terme (i,j) de \mathbf{A}^k donne le nombre de chemins de longueur exactement k allant de i à j.
Pourquoi
(\mathbf{A}^2)_{ij} = \sum_h a_{ih}a_{hj}
Chaque terme vaut 1 si et seulement s’il existe un arc de i vers h et un arc de h vers j. La somme compte les intermédiaires possibles.
Une conséquence utile
Si \mathbf{A} + \mathbf{A}^2 + \dots + \mathbf{A}^{n-1} n’a aucun zéro hors diagonale, le graphe est fortement connexe.
Tout se ramène ainsi à un produit de matrices — donc à quelque chose qu’un ordinateur fait très vite.
La matrice des valeurs
Quand les arcs sont pondérés
On remplace le 1 par la valeur de l’arc — distance, coût, durée, capacité —, et l’absence d’arc par +\infty.
L’infini plutôt que zéro
Mettre 0 ferait croire qu’aller de A à D est gratuit et instantané.
+\infty dit la vérité : ce trajet n’existe pas, et tout algorithme de minimisation l’écartera automatiquement.
La liste d’adjacence
L’autre représentation
Pour chaque sommet, la liste de ses successeurs :
A : (B,4), (C,2) \qquad B : (C,5), (D,10) \qquad C : (E,3) \quad \dots
Laquelle choisir
La matrice occupe n^2 cases, quel que soit le nombre d’arcs. Sur 10\,000 sommets, c’est cent millions de cases, presque toutes nulles.
La liste n’occupe que la place des arcs existants : c’est elle qu’utilisent tous les logiciels sur les grands réseaux.
Ce qu’il faut retenir
Le résumé du chapitre
Six points
- Un graphe est un couple (X, U) : sommets et arcs, orienté ou non.
- Source et puits se lisent sur les demi-degrés.
- La matrice d’adjacence code le graphe ; elle est symétrique si le graphe ne l’est pas orienté.
- (\mathbf{A}^k)_{ij} compte les chemins de longueur k de i à j.
- Pour un graphe pondéré, l’absence d’arc se note +\infty, jamais 0.
- La liste d’adjacence est préférable dès que le graphe est grand et peu dense.
La suite
Le chapitre 11 répond à la question laissée en suspens : trouver le plus court chemin de A à F, et le prouver, sans énumérer tous les trajets.
Ressources du chapitre
- Diapositives
- Polycopié du chapitre
- Exercices corrigés
- Application interactive
- — Vidéo
- QCM (bientôt)