108
Recherche opérationnelle
Dans certains problèmes, l'orientation des arcs n'importe pas : ce qu'il s'agit de savoir,
c'est si deux sommets sont reliés par un arc ou pas, et éventuellement le nombre d'arcs
reliant ces sommets.
Dans ces conditions, l'ordre
n'est plus important. On appellera arête toute paire de
sommets reliés par un arc, et au lieu de se donner la liste des arcs, on se donnera la liste
des arêtes. On obtiendra un graphe
sans orientation. On parlera alors de
multigraphe.
À un graphe orienté, on peut faire correspondre un multigraphe, en supprimant les
orientations. Par exemple, le graphe de la figure 1 donne le multigraphe suivant, si l'on
supprime les orientations des arcs :
Figure 2
Le concept de graphe est aujourd'hui très utilisé dans des disciplines diverses
(psychologie, sociologie, mathématique, etc.). En ce qui concerne la recherche
opérationnelle, nous allons voir que ce concept est particulièrement bien adapté au
traitement de certains problèmes combinatoires, c'est-à-dire de problèmes tels que
l'exploration systématique de toutes les solutions serait possible, mais s'avèrerait
beaucoup trop coûteuse en temps.
C'est ainsi que nous examinerons :
- des problèmes de « chemins minimaux ». (sur un graphe donné, par exemple
des villes - les sommets - et des routes - les arcs - où à chaque arc est associée
une longueur, trouver le chemin entre deux villes données qui soit de longueur
totale minimale)
- des problèmes de flots (sur un graphe donné représentant par exemple un réseau
de canalisations, où à chaque arc est associée une capacité, faire passer le flot
total maximal),
- des problèmes d'ordonnancement (par exemple le fameux problème du
voyageur de commerce, qui doit passer une fois et une seule dans un certain
nombre de villes et qui se pose la question de l'ordre de visite de ces villes de
façon que la distance totale parcourue soit la plus faible possible), ainsi qu'un
certain nombre d'autres problèmes que la théorie des graphes permet de
résoudre.
Recherche opérationnelle
Dans certains problèmes, l'orientation des arcs n'importe pas : ce qu'il s'agit de savoir,
c'est si deux sommets sont reliés par un arc ou pas, et éventuellement le nombre d'arcs
reliant ces sommets.
Dans ces conditions, l'ordre
n'est plus important. On appellera arête toute paire de
sommets reliés par un arc, et au lieu de se donner la liste des arcs, on se donnera la liste
des arêtes. On obtiendra un graphe
sans orientation. On parlera alors de
multigraphe.
À un graphe orienté, on peut faire correspondre un multigraphe, en supprimant les
orientations. Par exemple, le graphe de la figure 1 donne le multigraphe suivant, si l'on
supprime les orientations des arcs :
Figure 2
Le concept de graphe est aujourd'hui très utilisé dans des disciplines diverses
(psychologie, sociologie, mathématique, etc.). En ce qui concerne la recherche
opérationnelle, nous allons voir que ce concept est particulièrement bien adapté au
traitement de certains problèmes combinatoires, c'est-à-dire de problèmes tels que
l'exploration systématique de toutes les solutions serait possible, mais s'avèrerait
beaucoup trop coûteuse en temps.
C'est ainsi que nous examinerons :
- des problèmes de « chemins minimaux ». (sur un graphe donné, par exemple
des villes - les sommets - et des routes - les arcs - où à chaque arc est associée
une longueur, trouver le chemin entre deux villes données qui soit de longueur
totale minimale)
- des problèmes de flots (sur un graphe donné représentant par exemple un réseau
de canalisations, où à chaque arc est associée une capacité, faire passer le flot
total maximal),
- des problèmes d'ordonnancement (par exemple le fameux problème du
voyageur de commerce, qui doit passer une fois et une seule dans un certain
nombre de villes et qui se pose la question de l'ordre de visite de ces villes de
façon que la distance totale parcourue soit la plus faible possible), ainsi qu'un
certain nombre d'autres problèmes que la théorie des graphes permet de
résoudre.