Eulerian pathIn graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends on the same vertex. They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. The problem can be stated mathematically like this: Given the graph in the image, is it possible to construct a path (or a cycle; i.
Perfect matchingIn graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G = (V, E), a perfect matching in G is a subset M of edge set E, such that every vertex in the vertex set V is adjacent to exactly one edge in M. A perfect matching is also called a 1-factor; see Graph factorization for an explanation of this term. In some literature, the term complete matching is used. Every perfect matching is a maximum-cardinality matching, but the opposite is not true.
Graphe de PetersenLe graphe de Petersen est, en théorie des graphes, un graphe particulier possédant et . Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs. Il a cependant été mentionné par Alfred Kempe pour la première fois auparavant, en 1886.
TriangleEn géométrie euclidienne, un triangle est une figure plane formée par trois points (appelés sommets) et par les trois segments qui les relient (appelés côtés), délimitant un domaine du plan appelé intérieur. Lorsque les sommets sont distincts deux à deux, en chaque sommet les côtés délimitent un angle intérieur, d'où vient la dénomination de « triangle ». Le triangle est aussi le polygone le plus simple qui délimite une portion du plan et sert ainsi d'élément fondamental pour le découpage et l'approximation de surfaces.
Configuration de sommetEn géométrie, une configuration de sommet est une notation abrégée pour représenter la figure de sommet d'un polyèdre ou d'un pavage comme la séquence de faces autour d'un sommet. Pour les polyèdres uniformes, il n'y a qu'un seul type de sommet et, par conséquent, la configuration des sommets définit entièrement le polyèdre. (Les polyèdres chiraux existent dans des paires d'images miroir avec la même configuration de sommet). Une configuration de sommet est donnée sous la forme d'une suite de nombres représentant le nombre de côtés des faces faisant le tour du sommet.
Graphe de CayleyEn mathématiques, un graphe de Cayley (du nom d'Arthur Cayley) est un graphe qui encode la structure d'un groupe. C'est un outil important pour l'étude de la combinatoire et de la géométrie des groupes. Étant donné un groupe et une partie génératrice de ce groupe, le graphe de Cayley Cay(G,S) est construit comme suit : À chaque élément de , on associe un sommet . À chaque élément de , on associe une couleur . Pour tout et , on trace une arête orientée de couleur du sommet vers le sommet .
Couplage (théorie des graphes)En théorie des graphes, un couplage ou appariement (en anglais matching) d'un graphe est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun. Soit un graphe simple non orienté G = (S, A) (où S est l'ensemble des sommets et A l'ensemble des arêtes, qui sont certaines paires de sommets), un couplage M est un ensemble d'arêtes deux à deux non adjacentes. C'est-à-dire que M est une partie de l'ensemble A des arêtes telle que Un couplage maximum est un couplage contenant le plus grand nombre possible d'arêtes.
Graphe cycleLes graphes cycles, ou n-cycles, forment une famille de graphes. Le graphe cycle est constitué d'un unique cycle élémentaire de longueur n (pour ). C'est un graphe connexe non-orienté d'ordre n à n arêtes. Il est 2-régulier, c'est-à-dire que chacun de ses sommets est de degré 2. Beaucoup de termes sont employés pour désigner le graphe cycle : n-cycle, polygone et n-gone. Le terme de graphe cyclique est parfois employé, mais il pose problème car il s'oppose normalement à graphe acyclique. Nombre chromatique.
Degré (théorie des graphes)thumb|Un graphe non orienté où on a indiqué le degré de chaque sommet sur ce sommet. Dans ce graphe, le degré maximal est et le degré minimal est . En mathématiques, et plus particulièrement en théorie des graphes, le degré (ou valence) d'un sommet d'un graphe est le nombre de liens (arêtes ou arcs) reliant ce sommet, avec les boucles comptées deux fois. Le degré d'un sommet est noté . Dans le cas d'un graphe orienté, on parle aussi du degré entrant d'un sommet , c'est-à-dire le nombre d'arcs dirigés vers le sommet , et du degré sortant de ce sommet , c'est-à-dire le nombre d'arcs sortant de .
Graphe médialdroite|vignette|500x500px|Un graphe planaire (en bleu) et son graphe médial (en rouge). En théorie des graphes, le graphe médial du graphe planaire G est un graphe M(G) qui représente les adjacences entre les côtés des faces de G. Les graphes médiaux ont été introduits en 1922 par Ernst Steinitz dans l'étude des propriétés combinatoires des polyèdres convexes, bien que la construction inverse ait déjà été utilisée par Peter Tait en 1877, dans son étude fondamentale des nœuds et entrelacs Étant donné un graphe planaire G, son graphe médial M(G) est le graphe dont les sommets sont les arêtes de G, deux sommets étant reliés si les arêtes de G correspondantes sont consécutives dans une de ses faces.
