Exemples d'utilisation concrète de graphes et problèmes représentés
Apparition des graphes dans des problèmes concrets
On reconnaît que les graphes sont intéressants pour résoudre des problèmes concrets si on peut définir :
1) Un ensemble d'objets
2) Des causes de liens orientés (arcs) ou non orientés (arêtes) entre les objets
3) Des valeurs éventuelles associées aux liens
4) Des problèmes particuliers associés aux objets et aux liens
L'illustration suivante liste les grandes familles de problèmes de graphes les plus connus en précisant les quatre points qui précèdent.
Nous reviendrons ensuite de manière plus détaillée sur chacune de ses grandes familles de problèmes de graphes.
Exemple d'utilisations concrètes de graphes et notions représentées
Cliquez sur les flèches pour faire tourner les exemples proposés.
Exemples de problèmes concrets : chemins extrémaux
- Problème du voyageur de commerce visitant une et une seule fois chaque client.
- Organisation de tournées de collectes ou de distribution ou encore de déplacements d'objets entre des dépôts.
- Calcul des dates au plus tôt et des dates au plus tard des tâches en gestion de projet.
- Recherche des meilleures propositions pour composer un voyage avec plusieurs trains et/ou avions
- Recherche du chemin le plus rapide ou le plus court par un GPS.
En cliquant sur les boutons ci-dessous, vous pouvez obtenir un commentaire sonore sur les exemples concrets qui précèdent.
Notions liées à la connexité des graphes
- Existence d'une chaîne entre tout couple de points (connexité faible).
- Recherche des sous-graphes maximaux tels qu'il existe une chaîne entre tout couple de points (composantes connexes).
- Existence d'un chemin entre tout couple de points (connexité forte).
- Recherche des sous-graphes maximaux tels qu'il existe un chemin entre tout couple de points (composantes fortement connexes).
- Nombre minimal d'arcs ou d'arêtes à supprimer pour faire disparaître la connexité faible ou forte (k-connexité).
- Lorsque des coûts sont associés aux liaisons, recherche du graphe partiel de coût minimum qui soit k-connexe.
En cliquant sur les boutons ci-dessous, vous pouvez obtenir un commentaire détaillé sonore sur les notions concrètes qui précèdent.
Exemples de problèmes concrets : connexité
- Vérifier dans un réseau de transport que l'on peut bien se rendre de n'importe quel lieu à n'importe quel lieu.
- Intelligence des animaux
Le réseau souterrain du campagnol terrestre est 2-connexe.
- Minimiser le coût de constitution d'un réseau d'ordinateurs de manière à ce qu'ils puissent communiquer entre eux de manière directe ou indirecte
(arbre de recouvrement de coût minimal).
En cliquant sur les boutons ci-dessous, vous pouvez obtenir un commentaire sonore sur les exemples concrets qui précèdent.
Exemples de problèmes liés à la notion d'incompatibilité
- Sous-ensemble d'objets compatibles qui ne soit pas contenu strictement dans un autre ensemble d'objets compatibles
(recherche d'un stable maximal).
- Sous-ensemble d'objets compatibles dont le nombre d'objets soit maximum
(recherche d'un stable de cardinalité maximale).
- Partitionnement d'objets en sous-ensembles d'objets compatibles de telle sorte que le nombre de sous-ensembles de la partition soit minimum
(problème de coloration usuelle des points d'un graphe).
En cliquant sur les boutons ci-dessous, vous pouvez obtenir un commentaire détaillé sonore sur les notions concrètes qui précèdent.
Exemples de problèmes concrets d'incompatibilité
- Placer des examens ou des cours sur un planning sans qu'un même étudiant n'ait à suivre simultanément deux cours.
- Trouver un maximum d'objets compatibles entre eux pour les placer ensemble dans un four ou une suite de familles d'objets compatibles que l'on mettra successivement dans le four
(problème de constitution et de séquencement de batchs).
En cliquant sur les boutons ci-dessous, vous pouvez obtenir un commentaire sonore sur les exemples concrets qui précèdent.
Exemples de problèmes liés à la notion de préférence
- Analyse multicritère : sélection d'un sous-ensemble de solutions efficaces intéressant pour un groupe de décideurs.
- Trouver un ensemble de sommets incomparables entre eux mais tel que tout point qui n'est pas dans l'ensemble est moins bon au sens des préférences que au moins un point de l'ensemble
(notion de noyau ou anti-noyau).
La figure ci-dessous présente un graphe où la forme des points est carrée pour illustrer un anti-noyau de ce graphe et ronde pour les autres points.
En cliquant sur les boutons ci-dessous, vous pouvez obtenir un commentaire sonore sur les exemples concrets qui précèdent.
Exemples de problèmes d'affectation
- Affectation :
De personnel à des tâches
De clients à des dépôts
...
Couplage d'objets compatibles
- Trouver un couplage maximal entre deux sous-ensembles (disjoints) de points
(c'est-à-dire un ensemble d'arcs deux à deux non adjacents).
- Trouver un couplage maximal à coût minimal (méthode hongroise et problème de Hitchcock).
La figure ci-dessous présente un graphe bi-parti où la forme des points est carrée pour représenter un premier sous-ensemble de points et la forme est ronde pour représenter le deuxième sous-ensemble de points. Il est à noter qu'il n'y a pas de liens entre les points qui ont la même forme et que tous les liens vont des points carrés vers les points ronds.
En cliquant sur les boutons ci-dessous, vous pouvez obtenir un commentaire sonore sur les exemples concrets qui précèdent.
Exemples de problèmes de flots
Circulation :
- de liquide
- de gaz dans des conduites
- de véhicules sur des routes,
- de wagons et de locomotives pour réaliser des déplacements de trains adéquats.
Recherche d'un flot conservatif maximal traversant un graphe donné dont chaque arc est muni d'une limite de capacité supérieure.
Variante : capacités inférieures.
Variante : coefficients multiplicateurs pour le flot sur les arcs du réseau.
Trouver un flot conservatif maximal (ou fixé) pour un coût minimum.
En cliquant sur les boutons ci-dessous, vous pouvez obtenir un commentaire sonore sur les exemples concrets qui précèdent.
