GRAPHES THÉORIE DES

Article principal

• GRAPHES THÉORIE DES

  • Écrit par Hervé RAYNAUD
  • 3 604 mots
  • 10 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...

Articles associés

• ALGORITHMIQUE

  • Écrit par Philippe COLLARD, Philippe FLAJOLET
  • 6 652 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 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 426 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...

• CONVEXITÉ - Ensembles convexes

  • Écrit par Victor KLEE
  • 4 666 mots
  • 7 médias
  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'intersection...

• GRAPHES PARFAITS THÉORÈME FORT DES

  • Écrit par Vincent BARRÉ
  • 708 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...

• OPÉRATIONNELLE RECHERCHE

  • Écrit par Georges CULLMANN
  • 5 481 mots
  • 2 médias
  ...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éaire permettent heureusement une convergence vers la meilleure solution sans avoir à énumérer...

• PERCOLATION

  • Écrit par Jean ROUSSENQ
  • 1 952 mots
  • 3 médias
  ...duquel l'information ne percole pas d'un bout à l'autre du réseau. La réalité tient à la fois de l'un et de l'autre problème ; sa représentation est un graphe à deux dimensions. Il existe des cas particuliers simples où ce graphe est un réseau régulier. Celui-ci permet une simulation numérique de type...

• 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...

• QUATRE COULEURS PROBLÈME DES

  • Écrit par Jean MAYER
  • 2 176 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...

Médias