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).
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.
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.
CombinatoireEn mathématiques, la combinatoire, appelée aussi analyse combinatoire, étudie les configurations de collections finies d'objets ou les combinaisons d'ensembles finis, et les dénombrements. La combinatoire est en fait présente dans toute l'antiquité en Inde et en Chine. Donald Knuth, dans le volume 4A « Combinatorial Algorithms » de The Art of Computer Programming parle de la génération de n-uplets ; il dit que la génération de motifs combinatoires «a commencé alors que la civilisation elle-même prenait forme» (« began as civilization itself was taking shape»).
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.
Projective polyhedronIn geometry, a (globally) projective polyhedron is a tessellation of the real projective plane. These are projective analogs of spherical polyhedra – tessellations of the sphere – and toroidal polyhedra – tessellations of the toroids. Projective polyhedra are also referred to as elliptic tessellations or elliptic tilings, referring to the projective plane as (projective) elliptic geometry, by analogy with spherical tiling, a synonym for "spherical polyhedron".
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.
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.
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.
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.
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.
Graphe cordalthumb|Un cycle, en noir, avec deux cordes, en vert. Si l'on s'en tient à cette partie, le graphe est cordal. Supprimer l'une des arêtes vertes rendrait le graphe non cordal. En effet, l'autre arête verte formerait, avec les trois arêtes noires, un cycle de longueur 4 sans corde. En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle.
4 (nombre)4 (quatre) est l'entier naturel qui suit 3 et qui précède 5. Le préfixe du Système international pour 4 est tétra. La plupart des systèmes de numération possèdent un chiffre pour signifier le nombre quatre. Quatre (chiffre) Le chiffre « quatre », symbolisé « 4 », est le chiffre arabe servant notamment à signifier le nombre quatre. Le chiffre « 4 » n'est pas le seul utilisé dans le monde ; un certain nombre d'alphabets — particulièrement ceux des langues du sous-continent indien et du sud-est asiatique — utilisent des chiffres différents, même au sein de la numération indo-arabe.
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.
Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Line perfect graphIn graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle. A graph is line perfect if and only if each of its biconnected components is a bipartite graph, the complete graph K_4, or a triangular book K_1,1,n. Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect.
Optimisation combinatoireL’optimisation combinatoire, (sous-ensemble à nombre de solutions finies de l'optimisation discrète), est une branche de l'optimisation en mathématiques appliquées et en informatique, également liée à la recherche opérationnelle, l'algorithmique et la théorie de la complexité. Dans sa forme la plus générale, un problème d'optimisation combinatoire (sous-ensemble à nombre de solutions finies de l'optimisation discrète) consiste à trouver dans un ensemble discret un parmi les meilleurs sous-ensembles (ou solutions) réalisables, la notion de meilleure solution étant définie par une fonction objectif.
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.
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.
Convex polytopeA convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue.
