Combinatoire


ALGORITHMIQUE

  • Écrit par 
  • Philippe COLLARD, 
  • Philippe FLAJOLET
  •  • 6 677 mots
  •  • 5 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/4-algorithmes-combinatoires/

COMBINATOIRE ANALYSE

  • Écrit par 
  • Dominique FOATA
  •  • 5 442 mots
  •  • 3 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/analyse-combinatoire/#i_0

CONVEXITÉ - Ensembles convexes

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

Dans le chapitre « Aspects combinatoires »  : […] Intersections Une 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 Rn, […] Lire la suite☛ http://www.universalis.fr/encyclopedie/convexite-ensembles-convexes/3-aspects-combinatoires/

GRAPHES PARFAITS THÉORÈME FORT DES

  • Écrit par 
  • Vincent BARRÉ
  •  • 711 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/theoreme-fort-des-graphes-parfaits/#i_0

GRAPHES THÉORIE DES

  • Écrit par 
  • Hervé RAYNAUD
  •  • 3 616 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 de la théorie des graphes (Rome, 1966), déclarait : « Je […] Lire la suite☛ http://www.universalis.fr/encyclopedie/theorie-des-graphes/#i_0

OPÉRATIONNELLE RECHERCHE

  • Écrit par 
  • Georges CULLMANN
  •  • 5 496 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/recherche-operationnelle/2-les-etudes-combinatoires/

QUATRE COULEURS PROBLÈME DES

  • Écrit par 
  • Jean MAYER
  •  • 2 186 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 […] Lire la suite☛ http://www.universalis.fr/encyclopedie/probleme-des-quatre-couleurs/#i_0


Affichage 

Algorithmes de calcul de p

Algorithmes de calcul de p

tableau

Comparaison des approximations fournies par les trois algorithmes de calcul de p.… 

Crédits : Encyclopædia Universalis France

Afficher

Échelle de complexité

Échelle de complexité

tableau

Échelle de complexité. 

Crédits : Encyclopædia Universalis France

Afficher

Arbre binaire

Arbre binaire

dessin

Un arbre binaire de recherche associé à la suite x = 12, 9, 23, 6, 3, 18, 7 et sa lecture en projection. Chemins d'accès résultant de la recherche de 7 (A) et de la recherche de 20, non présent dans la suite x (B). 

Crédits : Encyclopædia Universalis France

Afficher

Arbre de sept sommets

Arbre de sept sommets

dessin

Arbre de sept sommets. 

Crédits : Encyclopædia Universalis France

Afficher

Nombres de Stirling

Nombres de Stirling

tableau

Nombres de Stirling de deuxième espèce. 

Crédits : Encyclopædia Universalis France

Afficher

Graphe de transport

Graphe de transport

dessin

Un graphe «de transport»… 

Crédits : Encyclopædia Universalis France

Afficher

Graphes orientés

Graphes orientés

dessin

Exemples de graphes orientés… 

Crédits : Encyclopædia Universalis France

Afficher

Ponts de Kœnigsberg

Ponts de Kœnigsberg

dessin

Le graphe associé au problème des ponts de Kœnigsberg. 

Crédits : Encyclopædia Universalis France

Afficher

Contraction

Contraction

dessin

Contraction d'un graphe… 

Crédits : Encyclopædia Universalis France

Afficher

Tournoi

Tournoi

dessin

Exemple de tournoi.    … 

Crédits : Encyclopædia Universalis France

Afficher

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

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

dessin

Une bonne représentation de K5 sur le tore… 

Crédits : Encyclopædia Universalis France

Afficher

Graphes de Kuratowski

Graphes de Kuratowski

dessin

Les deux graphes de Kuratowski… 

Crédits : Encyclopædia Universalis France

Afficher

Graphes non orientés

Graphes non orientés

dessin

Exemples de graphes non orientés… 

Crédits : Encyclopædia Universalis France

Afficher

Problème des trois maisons

Problème des trois maisons

dessin

Le problème des trois maisons… 

Crédits : Encyclopædia Universalis France

Afficher

Problème du coloriage

Problème du coloriage

dessin

Le problème du coloriage… 

Crédits : Encyclopædia Universalis France

Afficher

Empilements

Empilements

dessin

 

Crédits : Encyclopædia Universalis France

Afficher

Ensembles convexe et non convexe

Ensembles convexe et non convexe

dessin

 

Crédits : Encyclopædia Universalis France

Afficher

Graphe d'intersection

Graphe d'intersection

dessin

 

Crédits : Encyclopædia Universalis France

Afficher

Polyèdre de dimension 2

Polyèdre de dimension 2

dessin

 

Crédits : Encyclopædia Universalis France

Afficher

Hyperplan

Hyperplan

dessin

 

Crédits : Encyclopædia Universalis France

Afficher

Polytope de dimension 3

Polytope de dimension 3

dessin

 

Crédits : Encyclopædia Universalis France

Afficher

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

Réduction d'une configuration v 4  d'un graphe planaire triangulé

dessin

Réduction de v4. Les chiffres 1, 2, 3, 4 symbolisent les couleurs attribuées aux sommets. Si l'on trace un arc BD séparant A de C, on peut colorier les sommets C, C', C', etc., respectivement avec les couleurs 1, 3, 1, etc. Il est alors possible de colorier V en utilisant la couleur 3. 

Crédits : Encyclopædia Universalis France

Afficher

Réductibilité d'un quadrilatère

Réductibilité d'un quadrilatère

dessin

Réductibilité du quadrilatère (A. B. Kempe): dans un coloriage des régions, réduction d'une région ayant quatre voisines. C'est la réduction de la figure 1 présentée sous forme duale. Ici, on a colorié la carte, c'est-à-dire les régions et non les sommets. Dans le coloriage du bas, B,... 

Crédits : Encyclopædia Universalis France

Afficher

Algorithmes de calcul de p

Algorithmes de calcul de p
Crédits : Encyclopædia Universalis France

tableau

Échelle de complexité

Échelle de complexité
Crédits : Encyclopædia Universalis France

tableau

Arbre binaire

Arbre binaire
Crédits : Encyclopædia Universalis France

dessin

Arbre de sept sommets

Arbre de sept sommets
Crédits : Encyclopædia Universalis France

dessin

Nombres de Stirling

Nombres de Stirling
Crédits : Encyclopædia Universalis France

tableau

Graphe de transport

Graphe de transport
Crédits : Encyclopædia Universalis France

dessin

Graphes orientés

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

dessin

Ponts de Kœnigsberg

Ponts de Kœnigsberg
Crédits : Encyclopædia Universalis France

dessin

Contraction

Contraction
Crédits : Encyclopædia Universalis France

dessin

Tournoi

Tournoi
Crédits : Encyclopædia Universalis France

dessin

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

Représentation d'un graphe à 5 sommets sur le tore
Crédits : Encyclopædia Universalis France

dessin

Graphes de Kuratowski

Graphes de Kuratowski
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

Problème du coloriage

Problème du coloriage
Crédits : Encyclopædia Universalis France

dessin

Empilements

Empilements
Crédits : Encyclopædia Universalis France

dessin

Ensembles convexe et non convexe

Ensembles convexe et non convexe
Crédits : Encyclopædia Universalis France

dessin

Graphe d'intersection

Graphe d'intersection
Crédits : Encyclopædia Universalis France

dessin

Polyèdre de dimension 2

Polyèdre de dimension 2
Crédits : Encyclopædia Universalis France

dessin

Hyperplan

Hyperplan
Crédits : Encyclopædia Universalis France

dessin

Polytope de dimension 3

Polytope de dimension 3
Crédits : Encyclopædia Universalis France

dessin

Réduction d'une configuration v 4  d'un graphe planaire triangulé

Réduction d'une configuration v4 d'un graphe planaire triangulé
Crédits : Encyclopædia Universalis France

dessin

Réductibilité d'un quadrilatère

Réductibilité d'un quadrilatère
Crédits : Encyclopædia Universalis France

dessin

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
Crédits : Encyclopædia Universalis France

dessin