Combinatoire

Articles

ALGORITHMIQUE

Écrit par :  Philippe COLLARD, Philippe FLAJOLET

Dans le chapitre Algorithmes combinatoiresEntrent 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 ...  Lire la suite

COMBINATOIRE ANALYSE

Écrit par :  Dominique FOATA

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 dont elles dépend ...  Lire la suite

CONVEXITÉ - Ensembles convexes

Écrit par :  Victor KLEE

Dans le chapitre Aspects combinatoiresUne partie des problèmes combinatoires est reliée à l'étude des intersections d'ensembles convexes qui sont toujours convexes, comme on l'a vu ci-dessus (l'ensemble vide est, par définition, convexe). D'après un théorème démontré par Helly, l'intersection C d'une famille de convexes de Rⁿ, telle que l'intersection de t ...  Lire la suite

GRAPHES PARFAITS THÉORÈME FORT DES

Écrit par :  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 graphe G dans leque ...  Lire la suite

GRAPHES THÉORIE DES

Écrit par :  Hervé RAYNAUD

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 rem ...  Lire la suite

OPÉRATIONNELLE RECHERCHE

Écrit par :  Georges CULLMANN

Dans le chapitre Les études combinatoiresDans 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 et les techn ...  Lire la suite

QUATRE COULEURS PROBLÈME DES

Écrit par :  E.U.

Combinatoire ...  Lire la suite