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 e […]
… pour nos abonnés, l'article se prolonge sur 5 pages…
