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.
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.
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.
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.
Perfectly orderable graphIn graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.
List of graphsThis partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.
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.
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 de comparabilitéDans la théorie des graphes, un graphe de comparabilité est un graphe non orienté qui relie les paires d'éléments qui sont comparables les uns aux autres dans un ordre partiel donné. On les trouve aussi sous le nom de transitively orientable graphs, partially orderable graphs, et containment graphs. Les graphes de comparabilité sont des graphes parfaits. Les cographes sont des graphes de comparabilité Les graphes qui sont de comparabilité et dont le complémentaire est aussi de comparabilité sont exactement les graphes de permutations.
Graphe planaireDans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs.
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.
Points et parties remarquables de la frontière d'un convexeFace à un polyèdre convexe de l'espace de dimension 3, qu'il soit familier comme un cube ou plus compliqué, on sait spontanément reconnaître les points où le convexe est « pointu », ses sommets, puis subdiviser les points restants entre points des arêtes et points des faces. Cet article présente quelques définitions qui étendent ces concepts aux ensembles convexes généraux, de dimension quelconque, à la frontière éventuellement incurvée.
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.
CographeUn cographe est, en théorie des graphes, un graphe qui peut être généré par complémentation et union disjointe à partir du graphe à un nœud. La plupart des problèmes algorithmiques peuvent être résolus sur cette classe en temps polynomial, et même linaire, du fait de ses propriétés structurelles. Cette famille de graphe a été introduite par plusieurs auteurs indépendamment dans les années 1970 sous divers noms, notamment D*-graphes, hereditary Dacey graphs et 2-parity graphs.
Isomorphisme de graphesEn mathématiques, dans le cadre de la théorie des graphes, un isomorphisme de graphes est une bijection entre les sommets de deux graphes qui préserve les arêtes. Ce concept est en accord avec la notion générale d'isomorphisme, une bijection qui préserve les structures. Plus précisément, un isomorphisme f entre les graphes G et H est une bijection entre les sommets de G et ceux de H, telle qu'une paire de sommets {u, v} de G est une arête de G si et seulement si {ƒ(u), ƒ(v)} est une arête de H.
Graphe scindévignette|240x240px| Un graphe scindé, partitionné en une clique et un ensemble stable. En théorie des graphes, un graphe scindé ou graphe séparé (en anglais : split graph) est un graphe dont les sommets peuvent être partitionnés deux parties : une clique et un ensemble stable. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977, et introduit indépendamment par Tyshkevich et Tchernyak en 1979 .
Densité d'un grapheEn mathématiques, et plus particulièrement en théorie des graphes, on peut associer à tout graphe un entier appelé densité du graphe. Ce paramètre mesure si le graphe a beaucoup d'arêtes ou peu. Un graphe dense (dense graph) est un graphe dans lequel le nombre d'arêtes (ou d'arcs) est proche du nombre maximal, par exemple un nombre quadratique par rapport au nombre de sommets. Un graphe creux (sparse graph) a au contraire peu d'arêtes, par exemple un nombre linéaire. La distinction entre graphe creux et dense est plutôt vague et dépend du contexte.
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.
Graphe à distance héréditairevignette| Exemple d'un graphe à distance héréditaire. En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits.
