Diagramme de HasseEn mathématiques, le diagramme de Hasse, du nom du mathématicien allemand Helmut Hasse, est une représentation visuelle d'un ordre fini. Similaire à la représentation habituelle d’un graphe sur papier, il en facilite la compréhension. Dans un diagramme de Hasse : Les éléments ordonnés sont représentés par des points. La relation entre deux éléments est représentée par un segment entre deux points. Si un élément x est ≤ à un autre élément y, alors le point représentant x est placé plus bas que celui pour y.
Problème de plus court cheminvignette|Exemple d'un plus court chemin du sommet A au sommet F : (A, C, E, D, F). En théorie des graphes, le 'problème de plus court chemin' est le problème algorithmique qui consiste à trouver un chemin d'un sommet à un autre de façon que la somme des poids des arcs de ce chemin soit minimale. Il existe de nombreuses variantes de ce problème suivant que le graphe est fini, orienté ou non, que chaque arc ou arête possède ou non une valeur qui peut être un poids ou une longueur.
Feedback arc setvignette|Ce graphe orienté n'a pas de circuits: il n'est pas possible de partir d'un sommet quelconque et de revenir à ce même point, en suivant les connexions dans la direction indiquée par les flèches. En théorie des graphes, un graphe orienté peut contenir des circuits, c'est-à-dire des chemins qui reviennent sur leur point de départ. Dans certaines applications, ces circuits sont indésirables, et on cherche à les éliminer pour obtenir un graphe orienté acyclique (souvent abrégé en DAG).
Multi-arbreEn combinatoire et en théorie des ordres, le terme multi-arbre peut décrire l'une des deux structures suivantes : un graphe orienté acyclique dans lequel l'ensemble des sommets accessibles depuis un nœud est toujours un arbre, ou un ensemble partiellement ordonné dans lequel il n'existe pas quatre éléments a, b, c, et d qui forment un sous-ordre en diamant, avec et mais où b et c sont incomparables (un tel ensemble ordonné est aussi appelé diamond-free poset (ou ordre partiel sans diamant).
Citation graphA citation graph (or citation network), in information science and bibliometrics, is a directed graph that describes the citations within a collection of documents. Each vertex (or node) in the graph represents a document in the collection, and each edge is directed from one document toward another that it cites (or vice versa depending on the specific implementation). Citation graphs have been utilised in various ways, including forms of citation analysis, academic search tools and court judgements.
Boucle (théorie des graphes)In graph theory, a loop (also called a self-loop or a buckle) is an edge that connects a vertex to itself. A simple graph contains no loops. Depending on the context, a graph or a multigraph may be defined so as to either allow or disallow the presence of loops (often in concert with allowing or disallowing multiple edges between the same vertices): Where graphs are defined so as to allow loops and multiple edges, a graph without loops or multiple edges is often distinguished from other graphs by calling it a simple graph.
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.
Extension linéaireDans la branche des mathématiques de la théorie des ordres, une extension linéaire d'un ordre partiel est un ordre total (ou ordre linéaire) qui est compatible avec l'ordre partiel. Un exemple classique est l'ordre lexicographique des ensembles totalement ordonnés qui est une extension linéaire de leur ordre produit. Étant donnés des ordres partiels quelconques ≤ et ≤* sur un ensemble X, ≤* est une extension linéaire de ≤ si et seulement si (1) ≤* est un ordre total et (2) pour tout x et y dans X, si , alors .
Arborescence (graph theory)In graph theory, an arborescence is a directed graph in which, for a vertex u (called the root) and any other vertex v, there is exactly one directed path from u to v. An arborescence is thus the directed-graph form of a rooted tree, understood here as an undirected graph. Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root; a number of other equivalent characterizations exist. Every arborescence is a directed acyclic graph (DAG), but not every DAG is an arborescence.
Covering relationIn mathematics, especially order theory, the covering relation of a partially ordered set is the binary relation which holds between comparable elements that are immediate neighbours. The covering relation is commonly used to graphically express the partial order by means of the Hasse diagram. Let be a set with a partial order . As usual, let be the relation on such that if and only if and . Let and be elements of . Then covers , written , if and there is no element such that .
