Extrait du Chapitre 3 - Graphes, circuits et optimisation

Je veux que nous envoyions un homme sur la Lune, et qu’il revienne

sain et sauf sur la terre, et que cela soit fait avant la fin de la décennie.

John F. Kennedy, 25 mai 1961

 

Mon Dieu, ça y est, cette fois-ci nous devons vraiment le faire.

Robert F. Freitag (NASA)

Au cours de la seconde moitié du xxe siècle, la théorie des graphes connut un spectaculaire
essor dans le domaine mathématique. Elle acquit, en outre, une nouvelle
dimension en étant intégrée à de nombreuses applications liées à la planification et
à l’optimisation. Si ce développement fut soutenu par les progrès technologiques,
notamment dans le domaine florissant de l’informatique, l’idée de trouver des solutions
optimales, en temps ou en coûts, n’avait jamais suscité jusqu’alors une telle
recherche de méthodes et d’algorithmes efficaces. Des méthodes permettant de
proposer des solutions parfaitement adaptées furent adoptées dans des domaines
aussi divers que le lancement d’Apollo II par la NASA, le ramassage des ordures et
le nettoyage des grandes villes, les chaînes de production et de distribution de voitures
ou d’aliments… La recherche opérationnelle se révéla fructueuse et la théorie
des graphes suscita un intérêt toujours d’actualité. Le présent chapitre nous invite à
envisager le potentiel de cette théorie grâce à des problèmes d’optimisation pratiques.

Les circuits eulériens

Dans un graphe connexe, trouver un circuit d’Euler (ou eulérien) revient à déterminer
s’il est possible de partir d’un sommet du graphe et d’y revenir en ne passant qu’une
seule fois par toutes les arêtes du graphe (les sommets peuvent être répétés, mais pas
les arêtes). Dans la première des figures ci-après, on peut observer un circuit d’Euler,
tandis que dans le deuxième graphe il est impossible d’en trouver un.

Euler réussit parfaitement à expliquer pourquoi un graphe connexe donné est
un circuit eulérien en étudiant le concept fondamental de degré (ou valence) d’un
sommet, qui est le nombre d’arêtes ayant une extrémité en ce sommet. La clé du
problème est donnée par le théorème d’Euler suivant :

Il convient d’ajouter qu’en cas de circuit eulérien, toute arête fera partie d’une
paire. Chaque sommet aura donc un nombre pair d’arêtes, c’est-à-dire un degré pair.
Sachant cela, après avoir compté les degrés des sommets, on sait immédiatement s’il
y a un circuit eulérien. Cependant, il peut s’avérer beaucoup plus difficile de trouver
effectivement ce circuit.

Le problème du facteur chinois

Pour réaliser une tournée idéale, un facteur intelligent qui souhaite bien faire son
travail (parcourir toutes les rues où il doit remettre du courrier) ne devra passer
qu’une seule fois dans chaque rue. (...) Ce problème ayant été
étudié par le mathématicien chinois Meigu Guan en 1962, il est connu sous le nom
de « problème du facteur chinois ».

(...)

Au-delà des tournées de facteurs, le problème (..) peut s’avérer très utile
pour tout type de livraison (ou de collecte). Dans les grandes villes, que ce soit pour
le nettoyage des rues ou les diverses livraisons commerciales, disposer d’itinéraires
intelligents est un atout particulièrement intéressant en termes de coûts et de main
d’œuvre.

(...)

Sommaire du livre