Polytope abstraitEn mathématiques, et plus particulièrement en géométrie discrète, un polytope abstrait est un ensemble partiellement ordonné dont l'ordre reflète les propriétés combinatoires d'un polytope (au sens traditionnel, généralisant les polygones et les polyèdres à un nombre de dimensions quelconque), mais pas les aspects géométriques usuels, tels que les angles ou les distances. On dit qu'un polytope (géométrique) est une réalisation dans un espace à n dimensions (le plus souvent euclidien) du polytope abstrait correspondant.
PolytopeUn polytope est un objet mathématique géométrique. Le terme de polytope a été inventé par Alicia Boole Stott, la fille du logicien George Boole. Le terme polytope admet plusieurs définitions au sein des mathématiques. Principalement car les usages diffèrent en quelques points selon les pays, mais l'usage américain ayant tendance à s'imposer, on se retrouve confronté avec des usages contradictoires au sein d'un même pays.
PolyèdreUn polyèdre est une forme géométrique à trois dimensions (un solide géométrique) ayant des faces planes polygonales qui se rencontrent selon des segments de droite qu'on appelle arêtes. Le mot polyèdre, signifiant à plusieurs faces, provient des racines grecques πολύς (polys), « beaucoup » et ἕδρα (hedra), « base », « siège » ou « face ». Un polyèdre est un solide dont toutes les faces sont des polygones. Les côtés de ces polygones sont appelés arêtes. Les extrémités des arêtes sont des points appelés sommets.
Polytope régulierdroite|vignette|Le dodécaèdre régulier, un des cinq solides platoniciens. En mathématiques, plus précisément en géométrie ou encore en géométrie euclidienne, un polytope régulier est une figure de géométrie présentant un grand nombre de symétries. En dimension deux, on trouve par exemple le triangle équilatéral, le carré, les pentagone et hexagone réguliers, etc. En dimension trois se rangent parmi les polytopes réguliers le cube, le dodécaèdre régulier (ci-contre), tous les solides platoniciens.
Graphe bipartiEn théorie des graphes, un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints et tels que chaque arête ait une extrémité dans et l'autre dans . Un graphe biparti permet notamment de représenter une relation binaire. Il existe plusieurs façons de caractériser un graphe biparti. Par le nombre chromatique Les graphes bipartis sont les graphes dont le nombre chromatique est inférieur ou égal à 2. Par la longueur des cycles Un graphe est biparti si et seulement s'il ne contient pas de cycle impair.
Polyhedral combinatoricsPolyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes. Research in polyhedral combinatorics falls into two distinct areas. Mathematicians in this area study the combinatorics of polytopes; for instance, they seek inequalities that describe the relations between the numbers of vertices, edges, and faces of higher dimensions in arbitrary polytopes or in certain important subclasses of polytopes, and study other combinatorial properties of polytopes such as their connectivity and diameter (number of steps needed to reach any vertex from any other vertex).
Optimisation linéairethumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble admissible E est le pentagone vert. En optimisation mathématique, un problème d'optimisation linéaire demande de minimiser une fonction linéaire sur un polyèdre convexe. La fonction que l'on minimise ainsi que les contraintes sont décrites par des fonctions linéaires, d'où le nom donné à ces problèmes.
Semiregular polytopeIn geometry, by Thorold Gosset's definition a semiregular polytope is usually taken to be a polytope that is vertex-transitive and has all its facets being regular polytopes. E.L. Elte compiled a longer list in 1912 as The Semiregular Polytopes of the Hyperspaces which included a wider definition. In three-dimensional space and below, the terms semiregular polytope and uniform polytope have identical meanings, because all uniform polygons must be regular.
5-polytopeIn geometry, a five-dimensional polytope (or 5-polytope) is a polytope in five-dimensional space, bounded by (4-polytope) facets, pairs of which share a polyhedral cell. A 5-polytope is a closed five-dimensional figure with vertices, edges, faces, and cells, and 4-faces. A vertex is a point where five or more edges meet. An edge is a line segment where four or more faces meet, and a face is a polygon where three or more cells meet. A cell is a polyhedron, and a 4-face is a 4-polytope.
6-polytopeIn six-dimensional geometry, a six-dimensional polytope or 6-polytope is a polytope, bounded by 5-polytope facets. A 6-polytope is a closed six-dimensional figure with vertices, edges, faces, cells (3-faces), 4-faces, and 5-faces. A vertex is a point where six or more edges meet. An edge is a line segment where four or more faces meet, and a face is a polygon where three or more cells meet. A cell is a polyhedron. A 4-face is a polychoron, and a 5-face is a 5-polytope.
Dual d'un polyèdreEn géométrie, il existe plusieurs façons (géométrique, combinatoire) de mettre les polyèdres en dualité : on peut se passer de support géométrique et définir une notion de dualité en termes purement combinatoires, qui s'étend d'ailleurs aux polyèdres et polytopes abstraits. Dans chaque cas, à tout polyèdre est associé un polyèdre appelé dual du premier, tel que : le dual du polyèdre dual est le polyèdre initial, les faces de l'un sont en correspondance avec les sommets de l'autre, en respectant les propriétés d'adjacence.
4-polytopeEn géométrie, un 4-polytope (fréquemment appelé également un polychore) est un polytope de l'espace à quatre dimensions. C'est une figure connexe, composée d'un nombre fini de polytopes de dimension inférieure : des sommets, des arêtes, des faces (qui sont des polygones), et des cellules (qui sont des polyèdres), chaque face appartenant à exactement deux cellules. Le 4-polytope le plus connu est le tesseract (ou hypercube), analogue en 4D du cube. La définition des 4-polytopes varie beaucoup selon les auteurs.
Graphe parfaitEn théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.
Théorème des graphes parfaitsEn mathématiques, et plus précisément en théorie des graphes, le théorème des graphes parfaits (parfois appelé théorème fort des graphes parfaits) est une caractérisation des graphes parfaits par certains sous-graphes , conjecturée par Claude Berge en 1961. Maria Chudnovsky, Neil Robertson, Paul Seymour, et Robin Thomas en annoncèrent la démonstration en 2002, et la publièrent en 2006. Elle valut à leurs auteurs le prix Fulkerson de 2009.
Perfect graph theoremIn graph theory, the perfect graph theorem of states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by , and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs. A perfect graph is an undirected graph with the property that, in every one of its induced subgraphs, the size of the largest clique equals the minimum number of colors in a coloring of the subgraph.
Regular 4-polytopeIn mathematics, a regular 4-polytope is a regular four-dimensional polytope. They are the four-dimensional analogues of the regular polyhedra in three dimensions and the regular polygons in two dimensions. There are six convex and ten star regular 4-polytopes, giving a total of sixteen. The convex regular 4-polytopes were first described by the Swiss mathematician Ludwig Schläfli in the mid-19th century. He discovered that there are precisely six such figures.
Classe de complexitéEn informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.
Graphe trivialement parfaitvignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre. En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S.
Complexité paramétréeEn algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique.
Polyèdre flexibleEn géométrie, un polyèdre flexible, ou flexaèdre, est un polyèdre que l'on peut déformer continûment sans changer la forme de ses faces. Le théorème de rigidité de Cauchy montre qu'un tel polyèdre ne peut être convexe. Les premiers exemples de polyèdres flexibles, les , furent découverts par Raoul Bricard en 1897. Ce sont des surfaces auto-intersectantes (on parle parfois de polyèdres croisés, ou étoilés).
