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é.
Graphes orientés
Encyclopædia Universalis France
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,[...]
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Hervé RAYNAUD : professeur émérite de l'université Joseph Fourier
Classification
Médias
Graphes orientés
Encyclopædia Universalis France
Graphes non orientés
Encyclopædia Universalis France
Problème des trois maisons
Encyclopædia Universalis France
Autres références
-
PRIX ABEL 2021
- Écrit par Bernard PIRE
- 1 014 mots
- 2 médias
Le prix Abel, qui distingue chaque année un ou plusieurs mathématiciens pour leurs contributions exceptionnelles au développement des mathématiques, a été décerné en 2021 au Hongrois László Lovász et à l’Israélien Avi Wigderson. Dix-neuf ans après la création de ce « prix Nobel des...
-
ALGORITHMIQUE
- Écrit par Philippe COLLARD et Philippe FLAJOLET
- 6 654 mots
- 3 médias
...B : soit m la cardinalité de V ; il s'agit de déterminer s'il existe une permutation vσ(1), vσ(2), ..., vσ(m) de V telle que :– Le problème du coloriage de graphes. Étant donné un graphe G et un entier m, déterminer si G est m-coloriable, c'est-à-dire s'il existe une fonction...
-
BERGE CLAUDE (1926-2002)
- Écrit par Encyclopædia Universalis
- 207 mots
Mathématicien français. Fondateur de la théorie des graphes, écrivain cofondateur de l'Oulipo (« Ouvroir de littérature potentielle », en 1960), Claude Berge laisse aussi une œuvre de sculpteur et une collection d'objets d'art des Asmat de Nouvelle-Guinée. Docteur ès sciences mathématiques,...
-
COMBINATOIRE ANALYSE
- Écrit par Dominique FOATA
- 5 427 mots
- 2 médias
...élémentaires s'appliquent plus difficilement lorsqu'on veut dénombrer d'autres structures finies plus élaborées comme celles des arbres ou certains types de graphes. Le plus souvent on est conduit à chercher une correspondance biunivoque entre ces structures et les ensembles finis considérés dans la première... - Afficher les 9 références
