GRAPHES THÉORIE DES

Carte mentale

Élargissez votre recherche dans Universalis

Médias de l’article

Graphes orientés

Graphes orientés
Crédits : Encyclopædia Universalis France

dessin

Graphes non orientés

Graphes non orientés
Crédits : Encyclopædia Universalis France

dessin

Problème des trois maisons

Problème des trois maisons
Crédits : Encyclopædia Universalis France

dessin

Graphes de Kuratowski

Graphes de Kuratowski
Crédits : Encyclopædia Universalis France

dessin

Tous les médias


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ématiqu [...]


1  2  3  4  5
pour nos abonnés,
l’article se compose de 6 pages


Écrit par :

Classification


Autres références

«  GRAPHES THÉORIE DES  » est également traité dans :

ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 831 mots
  •  • 3 médias

Dans le chapitre « Algorithmes combinatoires »  : […] Entrent dans la catégorie des problèmes combinatoires , en informatique, les problèmes qui consistent à déterminer, pour une donnée  d , si est satisfaite une condition : où : ( a ) S( d ) est l'espace de recherche (l'espace des solutions potentielles) de taille exponentielle en la taille de d […] Lire la suite☛ http://www.universalis.fr/encyclopedie/algorithmique/#i_35345

BERGE CLAUDE (1926-2002)

  • Écrit par 
  • Universalis
  •  • 208 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, chercheur au C.N.R.S. dès 1952, directeur du Centre international de calcul à Rome (1965-1967), enseignan […] Lire la suite☛ http://www.universalis.fr/encyclopedie/claude-berge/#i_35345

COMBINATOIRE ANALYSE

  • Écrit par 
  • Dominique FOATA
  •  • 5 830 mots
  •  • 2 médias

Dans le chapitre « Construction de correspondances »  : […] Dans la première partie, nous avons passé en revue tous les ensembles finis qu'il était aisé de dénombrer en faisant usage des deux règles de la somme et du produit. Ces techniques é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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/analyse-combinatoire/#i_35345

CONVEXITÉ - Ensembles convexes

  • Écrit par 
  • Victor KLEE
  •  • 4 793 mots
  •  • 7 médias

Dans le chapitre « Théorèmes de séparation »  : […] En analyse fonctionnelle, en théorie des jeux, en intégration et même dans certains problèmes relatifs aux graphes coloriés en théorie des graphes, on utilise des théorèmes de séparation et de support. Les théorèmes de séparation établissent les conditions sous lesquelles on peut séparer (au sens du chapitre 1) deux sous-ensembles convexes disjoints X et Y d'un espace vectoriel topologique E. Pou […] Lire la suite☛ http://www.universalis.fr/encyclopedie/convexite-ensembles-convexes/#i_35345

GRAPHES PARFAITS THÉORÈME FORT DES

  • Écrit par 
  • Vincent BARRÉ
  •  • 716 mots

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 graphe G dans lequel les conférences seront représentées […] Lire la suite☛ http://www.universalis.fr/encyclopedie/theoreme-fort-des-graphes-parfaits/#i_35345

OPÉRATIONNELLE RECHERCHE

  • Écrit par 
  • Georges CULLMANN
  •  • 5 547 mots
  •  • 2 médias

Dans le chapitre « Les études combinatoires »  : […] Dans ce contexte déterminé, les éléments nécessaires au calcul des décisions sont connus avec exactitude, à la précision des mesures près éventuellement. La principale difficulté réside dans le très grand nombre de solutions possibles entre lesquelles le choix doit s'exercer pour ne retenir que la plus favorable. Les algorithmes de la théorie des graphes et les techniques de programmation linéair […] Lire la suite☛ http://www.universalis.fr/encyclopedie/recherche-operationnelle/#i_35345

PERCOLATION

  • Écrit par 
  • Jean ROUSSENQ
  •  • 1 952 mots
  •  • 3 médias

Dans le chapitre « Modèles »  : […] Un système de communication rapide à grande distance peut être constitué par un réseau de stations, placées sur des hauteurs, à partir desquelles des opérateurs relaient des signaux optiques. Chaque station est en vue de plusieurs autres. L'ennemi fondamental du système est le manque de visibilité pour cause météorologique, coupant le lien entre deux stations. Dans ce cas, il est encore possible d […] Lire la suite☛ http://www.universalis.fr/encyclopedie/percolation/#i_35345

QUATRE COULEURS PROBLÈME DES

  • Écrit par 
  • Jean MAYER
  •  • 2 243 mots
  •  • 2 médias

Résolu en 1976 par Kenneth Appel et Wolfgang Haken de l'université d'Illinois, le problème des quatre couleurs offre une triple particularité : sa popularité, due à la simplicité suggestive de son énoncé ; les nombreux efforts faits pour le résoudre, qui ont fécondé toute la branche de la topologie combinatoire appelée théorie des graphes (cf. théorie des graphes , en par […] Lire la suite☛ http://www.universalis.fr/encyclopedie/probleme-des-quatre-couleurs/#i_35345

Voir aussi

Pour citer l’article

Hervé RAYNAUD, « GRAPHES THÉORIE DES », Encyclopædia Universalis [en ligne], consulté le 16 octobre 2019. URL : http://www.universalis.fr/encyclopedie/theorie-des-graphes/