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 […]
Autres références
« GRAPHES THÉORIE DES » est également traité dans :
-
ALGORITHMIQUE
Auteurs :
Philippe COLLARD, Philippe FLAJOLET
Dans le chapitre "Algorithmes combinatoires" : …
σ(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 f de l'ensemble des sommets de G dans {1, 2, ..., m} telle…
Lire la suite
-
BERGE CLAUDE (1926-2002)
Auteur :
E.U.
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, chercheur au C.N.R.S. dès 1952, directeur du Centre…
Lire la suite
-
COMBINATOIRE ANALYSE
Auteur :
Dominique FOATA
Dans le chapitre "Construction de correspondances" : …
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 partie. Jusqu'ici, il n'existe pas de théorie pour construire ces correspondances, tout est…
Lire la suite
-
CONVEXITÉ - Ensembles convexes
Auteur :
Victor KLEE
Dans le chapitre "Aspects combinatoires" : …
L'étude des propriétés des intersections d'ensembles convexes est facilitée par la notion de *graphe d'intersection, qui est utilisée dans des domaines aussi variés que la génétique moléculaire, la psychologie et l'écologie. Pour toute famille d'ensembles, on appelle graphe d'intersectionun graphe abstrait où chaque ensemble…
Lire la suite
-
GRAPHES PARFAITS THÉORÈME FORT DES
Auteur :
Vincent BARRÉ
*Vous organisez un colloque dans lequel plusieurs conférences sont données simultanément (dans des salles différentes et à des horaires imposés par les orateurs) et vous cherchez à occuper le moins de salles possibles (car vous devez les louer). Une méthode permettant de réaliser un tel planning consiste à construire un grapheG dans lequel…
Lire la suite
Afficher la liste complète (8 références)
Retour en haut
Bibliographie
K. Appel & W. Haken, « Every Planar Graph is Four Colorable », in Illinois J. Math., 21, pp. 429-567, 1977
C. Berge, Théorie des graphes et ses applications, 3e éd., Gauthier-Villars, Paris, 1983
Graphes et hypergraphes, Dunod, Paris, 2e éd. 1973
C. Berge,Graphs, Elsevier Science Publ., New York, 1992
C. Berge & V. Chvátal éd., Topics on Perfect Graphs, Annals of Discrete Maths, 21, North Holland, Amsterdam, 1984
N. L. Biggs, E. K. Lloyd & R. J. Wilson, Graph Theory : 1736-1936, Clarendon Press, Oxford, 1977
V. Chachra, Applications of Graph Theory Algorithms, North-Holland-New York, 1979
N. Deo, Graph Theory with Applications to Engineering and Computer Science, Prentice-Hall, Englewood Cliffs, 1974
F. Harary, R. Z. Normann & D. Cartwright, Introduction à la théorie des graphes orientés. Modèles structuraux, Dunod, 1968
R. Nelson & J. R. Wilson, Graph Colourings, Halsted Press, New York, 1990
O. Ore, Graphs and Their Uses, Mathematical Association of America, Washington (D.C.), 1990
Theory of Graphs, A.M.S., Providence, repr. of 1962, ibid., 1987
N. Robertson, D. P. Sanders, P. Seymour & R. Thomas, « A New Proof of the Four-Colour Theorem », in Electronic Research Announcements of the American Mathematical Society, vol. 2, n° 1, août 1996 (électronique)
R. J. Wilson, Introduction to Graph Theory, 3e éd., Wiley, New York, 1986.
Retour en haut
