Concept
Graphe biparti
Concepts associés (51)
Nombre achromatique
En théorie des graphes, une coloration complète est l'opposé d'une coloration harmonieuse en ce sens que c'est une coloration des sommets dans laquelle toute paire de couleurs apparait au moins sur une paire de sommets adjacents. Le nombre achromatique ψ(G) d'un graphe G est le nombre maximum de couleurs possibles dans une coloration complète de G. right|300px|thumb|Coloration complète du graphe de Clebsch avec 8 couleurs. Dans la figure ci-contre, on a réussi à colorier le graphe de Clebsch avec huit couleurs, de manière que chaque paire de couleurs apparaisse sur au moins une arête.
List of graphs
This 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.
Lemme des poignées de main
vignette|250px|Dans ce graphe, un nombre pair de sommets (les quatre sommets numérotés 2, 4, 5, et 6) a des degrés impairs. La somme des degrés des sommets vaut 2 + 3 + 2 + 3 + 3 + 1 = 14, deux fois le nombre d'arêtes. En théorie des graphes, une branche des mathématiques, le lemme des poignées de main est la déclaration selon laquelle chaque graphe non orienté fini a un nombre pair de sommets de degré impair. Plus trivialement, dans une réunion de plusieurs personnes dont certaines se serrent la main, un nombre pair de personnes devra serrer un nombre impair de fois la main d'autres personnes.
Arête transversale
En théorie des hypergraphes, une transversale est une partie des sommets qui rencontre toutes les arêtes d'un hypergraphe. L'ensemble des transversales est la grille. C'est l'analogue du problème de couverture par sommets (vertex cover en anglais) chez les graphes. On rappelle qu'un hypergraphe est un couple où est un ensemble de sommets, et une famille de sous-ensembles de qu'on nomme arêtes, ou hyperarêtes. Une transversale de est un ensemble tel que pour toute arête appartenant à , .
Graphe de Heawood
En théorie des graphes, le graphe de Heawood est un graphe cubique symétrique possédant 14 sommets et 21 arêtes. Il doit son nom à Percy John Heawood, un mathématicien britannique né en 1861 et mort en 1955. Le graphe de Heawood est une (3,6)-cage, c'est-à-dire un graphe minimal en nombres de sommets ayant une maille de 6 et étant cubique. En fait, il s'agit de l'unique (3,6)-cage et sa taille coïncide avec la borne de Moore, une borne inférieure sur le nombre de sommets que peut avoir une cage.
Factor graph
A factor graph is a bipartite graph representing the factorization of a function. In probability theory and its applications, factor graphs are used to represent factorization of a probability distribution function, enabling efficient computations, such as the computation of marginal distributions through the sum-product algorithm. One of the important success stories of factor graphs and the sum-product algorithm is the decoding of capacity-approaching error-correcting codes, such as LDPC and turbo codes.
Bipartite double cover
In graph theory, the bipartite double cover of an undirected graph G is a bipartite, covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs, G × K_2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G. It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice. The bipartite double cover of G has two vertices u_i and w_i for each vertex v_i of G.
Signed graph
In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign. A signed graph is balanced if the product of edge signs around every cycle is positive. The name "signed graph" and the notion of balance appeared first in a mathematical paper of Frank Harary in 1953. Dénes Kőnig had already studied equivalent notions in 1936 under a different terminology but without recognizing the relevance of the sign group.
Multipartite graph
In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are (or can be) partitioned into k different independent sets. Equivalently, it is a graph that can be colored with k colors, so that no two endpoints of an edge have the same color. When k = 2 these are the bipartite graphs, and when k = 3 they are called the tripartite graphs. Bipartite graphs may be recognized in polynomial time but, for any k > 2 it is NP-complete, given an uncolored graph, to test whether it is k-partite.
Total coloring
In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges, no adjacent vertices and no edge and either endvertex are assigned the same color. The total chromatic number χ′′(G) of a graph G is the fewest colors needed in any total coloring of G.