GRAPHES THÉORIE DES

On appelle théorie des graphes une classe de problèmes d'apparence hétéroclite, plus ou moins bien résolus, mais qui suscite un engouement à la hauteur de la fascination qu'exercent ses résultats.

Claude Berge (1926-2002), dans son discours inaugural des Journées internationales d'études de la théorie des graphes (Rome, 1966), déclarait : « Je remercie les deux cent cinquante participants de ce congrès, venus si nombreux à Rome pour un sujet qui, il y a dix ans seulement, n'aurait attiré qu'une dizaine de personnes. Étrange évolution que celle de la théorie des graphes, qui se développe par à-coups, sous l'impulsion tour à tour du rôle de l'électricité, de la géométrie des polyèdres, de la théorie des jeux, et surtout maintenant de la recherche opérationnelle et du calcul électronique... »

Aujourd'hui, des centaines de congrès numériquement beaucoup plus importants ont eu lieu sur le même sujet. De très nombreux domaines d'application se sont ouverts, allant de la sociologie à la chimie en passant évidemment par les besoins des réseaux de communication ...

Depuis 1966, les Mathematical Reviews, périodique qui recense et résume la plupart des articles mathématiques parus, ont ouvert une rubrique intitulée « Théorie des graphes ». Située dans cette publication entre la théorie des ensembles et la logique mathématique, elle rend compte aujourd'hui de très fréquents articles.

On peut dire qu'il s'agit d'une théorie relativement récente. L'originalité de son champ propre, du point de vue psychologique, est étonnante. Ses concepts et ses problèmes, particulièrement compliqués, arbitraires et rébarbatifs dans leur écriture formelle, peuvent être facilement compris par les non-spécialistes. Il suffit pour cela de consentir à ce que de petits dessins, auxquels les théoriciens des graphes ont systématiquement recours, fécondent l'intuition.

Nous présenterons dans cet article quelques grands problèmes de la théorie des graphes. Le lecteur vérifiera facilement que l'exposé formel en serait peu séduisant, et l'intérêt de leurs solutions à peu près incompréhensible. Nous signalerons a contrario, pour finir, un domaine de la théorie pour lequel l'algébrisation des concepts a atteint une grande rigueur, rigueur qui reste cette fois justifiée par l'efficacité des notions ainsi introduites.

Définitions

Les nombreuses définitions des graphes caractérisent en fait des objets très similaires. Ces définitions ne sont pas toujours du même type algébrique. Tel auteur précisera que les graphes qu'il considère sont essentiellement finis, tel autre réservera le nom de graphes aux graphes non orientés, tel autre encore dira qu'un graphe est une correspondance d'un ensemble fini dans lui-même...

Cet article se limitera à ce que l'on appelle souvent multigraphes, orientés ou non, en omettant, comme la grande majorité des auteurs, le préfixe multi, et en permettant les boucles sur les sommets.

Graphes orientés

Plus précisément, on appellera graphe orienté un quadruplet (X, U, o, e), où X désigne un ensemble appelé ensemble des sommets du graphe ; U un ensemble appelé ensemble des arcs du graphe ; o une application de U dans X appelée origine ; e une application de U dans X appelée extrémité.

Cette définition, pour correcte qu'elle soit, n'offre certes pas un support bien engageant pour l'intuition. Et pourtant, si l'on accepte de représenter les éléments de X par des points du plan, et tout élément de U par une « flèche » partant du point représentatif de son image par o pour aboutir au point représentatif de son image par e, on obtient de petits dessins du genre de ceux de la figure.

De tels dessins évoquent des problèmes réels tels qu'il s'en pose en sociologie, en recherche opérationnelle, en physique,[...]