Concept
Graphe cycle
Concepts associés (26)
Graphe couronne
En théorie des graphes, une branche des mathématiques, un graphe couronne à 2 n sommets est un graphe non orienté comportant deux jeux de sommets ui et vi reliés par une arête de ui à vj à chaque fois que i ≠ j. Le graphe couronne à six sommets est un graphe cycle. Le graphe couronne à huit sommets est le graphe hexaédrique, celui qui décrit les sommets et les arêtes d'un cube. Le graphe couronne peut être vu comme un graphe biparti complet d'où l'on aurait retiré les arêtes formant un couplage parfait (les arêtes horizontales absentes sur la figure).
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.
Hamiltonian path
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.
Produit cartésien (graphe)
Le produit cartésien, ou somme cartésienne, est une opération sur deux graphes et résultant en un graphe . Parler de produit ou de somme pour cette opération n'est pas une contradiction, mais une explication basée sur deux aspects différents : la construction peut se voir comme un produit, tandis que de nombreuses propriétés sont basées sur la somme. Soient deux graphes et . Le produit cartésien est défini comme suit : Autrement dit, l'ensemble résultant des sommets est le produit cartésien .
Universal vertex
In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused with a universally quantified vertex in the logic of graphs.) A graph that contains a universal vertex may be called a cone. In this context, the universal vertex may also be called the apex of the cone.
Graphe roue
En théorie des graphes, le graphe roue Wn est un graphe d'ordre formé en ajoutant un sommet « centre » connecté à tous les sommets du graphe cycle Cn-1. La notation Wn provient du nom anglais wheel graph mais n'est pas universelle. Certains auteurs préfèrent Wn-1, faisant référence à la longueur du cycle. Pour les valeurs impaires de n, le graphe Wn est un graphe parfait. Quand n est pair et supérieur ou égal à 6, le graphe roue Wn n'est pas parfait.