Graphe à seuilvignette| Un graphe à seuil. En théorie des graphes, un graphe à seuil est un graphe qui peut être construit, en partant d'un graphe à un seul sommet, par application répétée d'une des deux opérations suivantes : Ajout d'un sommet isolé au graphe. Ajout d'un sommet dominant au graphe, c'est-à-dire d'un sommet connecté à tous les autres sommets. Par exemple, le graphe de la figure ci-contre est un graphe de seuil : il peut être construit en commençant par un graphe à un seul sommet (sommet 1), puis en ajoutant les sept autres dans l'ordre dans lequel ils sont numérotés, les sommets noirs comme sommets isolés et les sommets rouges comme sommets dominants.
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.
Claw-free graphIn graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph comprising three edges, three leaves, and a central vertex). A claw-free graph is a graph in which no induced subgraph is a claw; i.e., any subset of four vertices has other than only three edges connecting them in this pattern. Equivalently, a claw-free graph is a graph in which the neighborhood of any vertex is the complement of a triangle-free graph.
Pseudo-forêtvignette|upright=1.2 |Une 1-forêt (une pseudo-forêt maximale), composée de trois 1-arbres En théorie des graphes, une pseudo-forêt est un graphe non orienté, ou même un multigraphe dans lequel chaque composante connexe possède au plus un cycle. De manière équivalente, une pseudo-forêt est un graphe dans lequel deux cycles ne sont pas connectés par une chaîne. Un pseudo-arbre est une pseudo-forêt connexe. Les noms évoquent l'analogie avec les arbres et les forêts plus couramment étudiés : un arbre est un graphe connexe sans cycle ; une forêt est une union disjointe d'arbres.
Ensemble dominantEn théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donné G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.
Apex graphIn graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K_5 or K_3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.
Wagner's theoremIn graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.
Mineur (théorie des graphes)La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. Soit un graphe non orienté fini. Un graphe est un mineur de s'il peut être obtenu en contractant des arêtes d'un sous-graphe de .
Largeur arborescenteEn théorie des graphes et en informatique théorique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre qui, intuitivement, mesure s'il est proche d'un arbre. Elle peut être définie de plusieurs manières, notamment en utilisant la décomposition arborescente. Souvent, un problème algorithmique facile sur les arbres est en fait facile pour les graphes qui ressemblent à des arbres. Ainsi, ce paramètre est souvent utilisé en algorithmique de graphes, notamment pour les schémas d'approximation polynomiaux et complexité paramétrée.
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.
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.
Linkless embeddingIn topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.
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 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 .
Graph operationsIn the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations. Unary operations create a new graph from a single initial graph. Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc.
Graphe cactusvignette|upright=1.4| Un graphe cactus. En théorie des graphes, un graphe cactus (parfois appelé arbre cactus) est un graphe connexe dans lequel deux cycles simples quelconques ont au plus un sommet en commun. De manière équivalente, c'est un graphe connexe dans lequel chaque arête appartient à au plus un cycle simple, ou (pour les cactus non triviaux) dans lequel chaque bloc (sous-graphe maximal sans point d'articulation) est une arête ou un cycle.
Graphe dualEn théorie des graphes, le graphe dual d'un graphe plongé dans une surface est défini à l'aide des composantes de son complémentaire, lesquelles sont reliées entre elles par les arêtes du graphe de départ. Cette notion généralise celle de dualité dans les polyèdres. Il faut noter qu'un même graphe abstrait peut avoir des graphes duaux non isomorphes en fonction du plongement choisi, même dans le cas de plongements dans le plan. Un graphe (plongé) isomorphe à son dual est dit autodual.
Graphe toroïdalright|frame| Un graphe plongé sur le tore de telle façon que les arêtes ne se coupent pas. En mathématiques, et plus précisément en théorie des graphes, un graphe G est toroïdal s'il peut être plongé sur le tore, c'est-à-dire que les sommets du graphe peuvent être placés sur le tore de telle façon que les arêtes ne se coupent pas. En général dire qu'un graphe est toroïdal sous-entend également qu'il n'est pas planaire.
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 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.
