Abonnez-vous à Universalis pour 1 euro

Combinatoire

Articles

  • ALGORITHMIQUE

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

    L'objet de l'algorithmique est la conception, l'évaluation et l'optimisation des méthodes de calcul en mathématiques et en informatique. Un algorithme consiste en la spécification d'un schéma de calcul, sous forme d'une suite d'opérations élémentaires obéissant à un enchaînement déterminé....

  • COMBINATOIRE ANALYSE

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

    L'analyse combinatoire est l'ensemble des techniques qui servent, en mathématiques, à compter (ou dénombrer) certaines structures finies, ou à les énumérer (établir des listes exhaustives de structures considérées), enfin à démontrer leur existence pour certaines valeurs des paramètres...

  • CONVEXITÉ - Ensembles convexes

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

    Un sous-ensemble C d'un espace vectoriel réel E est dit convexe si, pour tout couple de points quelconques de C, le segment qui a pour extrémités ces deux points est entièrement contenu dans C. Par exemple, un cube est convexe, mais sa surface ne l'est pas, car elle ne contient le segment d'extrémités...

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

  • 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

    Bien conjecturer a toujours été le principal souci de l'homme ; il a rapidement eu conscience des avantages qu'il pouvait tirer de la prévision d'une conjoncture. Les moyens ont évolué, la complexité des problèmes à résoudre est devenue telle qu'il n'est plus possible aujourd'hui de...

  • 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

Algorithmes de calcul de p

Algorithmes de calcul de p

Arbre binaire

Arbre binaire

Arbre de sept sommets

Arbre de sept sommets

Contraction

Contraction

Échelle de complexité

Échelle de complexité

Empilements

Empilements

Ensembles convexe et non convexe

Ensembles convexe et non convexe

Graphe de transport

Graphe de transport

Graphe d'intersection

Graphe d'intersection

Graphes de Kuratowski

Graphes de Kuratowski

Graphes non orientés

Graphes non orientés

Graphes orientés

Graphes orientés

Hyperplan

Hyperplan

Nombres de Stirling

Nombres de Stirling

Opérations à effectuer et étapes à parcourir de l'origine à la fin des travaux

Opérations à effectuer et étapes à parcourir de l'origine à la fin des travaux

Polyèdre de dimension 2

Polyèdre de dimension 2

Polytope de dimension 3

Polytope de dimension 3

Ponts de Kœnigsberg

Ponts de Kœnigsberg

Problème des trois maisons

Problème des trois maisons

Problème du coloriage

Problème du coloriage

Réductibilité d'un quadrilatère

Réductibilité d'un quadrilatère

Réduction d'une configuration v<inf>4</inf> d'un graphe planaire triangulé

Réduction d'une configuration v4 d'un graphe planaire triangulé

Représentation d'un graphe à 5 sommets sur le tore

Représentation d'un graphe à 5 sommets sur le tore

Tournoi

Tournoi