Concept
Reachability
Concepts associés (12)
Graphe orienté
thumb|Un graphe orienté .(Figure 1) Dans la théorie des graphes, un graphe orienté est un couple formé de un ensemble, appelé ensemble de nœuds et un ensemble appelé ensemble d'arêtes. Les arêtes sont alors nommées arcs, chaque arête étant un couple de noeuds, représenté par une flèche. Étant donné un arc , on dit que est l'origine (ou la source ou le départ ou le début) de et que est la cible (ou l'arrivée ou la fin) de . Le demi-degré extérieur (degré sortant) d'un nœud, noté , est le nombre d'arcs ayant ce nœud pour origine.
Transitive reduction
In the mathematical field of graph theory, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by , who provided tight bounds on the computational complexity of constructing them. More technically, the reduction is a directed graph that has the same reachability relation as D.
Tri topologique
En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. Soit un graphe orienté avec et . Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7, 1, 2, 9, 8, 4, 3, 5, 6.
Fermeture transitive
La fermeture transitive est une opération mathématique pouvant être appliquée sur des relations binaires sur un ensemble, autrement dit sur des graphes orientés. La clôture transitive, ou fermeture transitive R d'une relation binaire R sur un ensemble X est la relation ce qui peut également se traduire ainsi : Si on nomme la relation "il existe un chemin de taille n entre a et b" On définit C'est la plus petite relation transitive sur X contenant R.
Polyarbre
En mathématiques, et notamment en théorie des graphes, un polyarbre (aussi appelé arbre dirigé, arbre orienté ou singly connected network) est graphe orienté acyclique dont le graphe non orienté sous-jacent est un arbre (théorie des graphes). En d'autres termes, si on remplace les arcs par des arêtes, on obtient un graphe non orienté qui est à la fois connexe et sans cycle. Une polyforêt (ou forêt dirigée ou forêt orientée) est un graphe orienté dont le graphe non orienté sous-jacent est une forêt.
Graphe orienté acyclique
En théorie des graphes, un graphe orienté acyclique (en anglais directed acyclic graph ou DAG), est un graphe orienté qui ne possède pas de circuit. Un tel graphe peut être vu comme une hiérarchie. Un graphe orienté acyclique est un graphe orienté qui ne possède pas de circuit. On peut toujours trouver un sous-graphe couvrant d’un graphe orienté acyclique qui soit un arbre (resp. une forêt). Dans un graphe orienté acyclique, la relation d'accessibilité R(u, v) définie par « il existe un chemin de u à v » est une relation d'ordre partielle.
Préordre
En mathématiques, un préordre est une relation binaire réflexive et transitive. C'est-à-dire que si E est un ensemble, une relation binaire sur E est un préordre lorsque : (réflexivité) ; (transitivité). Un ensemble préordonné est un ensemble muni d'un préordre, ou plus formellement un couple où désigne un ensemble et un préordre sur . Les ordres sont les préordres antisymétriques. Les relations d'équivalence sont les préordres symétriques. Dans un anneau commutatif, la relation « divise » est une relation de préordre.
Lexique de la théorie des graphes
NOTOC Acyclique graphe ne contenant pas de cycle. Adjacence une liste d'adjacence est une structure de données constituée d'un tableau dont le -ème élément correspond à la liste des voisins du -ème sommet. Adjacence une matrice d'adjacence est une matrice carrée usuellement notée , de dimensions , dont chaque élément est égal au nombre d'arêtes incidentes (ayant pour extrémités) aux sommets d'indices et (pour un graphe simple non pondéré, ). Dans le cas d'un graphe pondéré, chaque élément est égal à la somme du poids des arêtes incidentes.
Cycle (théorie des graphes)
thumb|Dans ce graphe, le cycle rouge est élémentaire. Le cycle bleu ne l'est pas. La chaine verte n'est pas fermée et ne forme donc pas un cycle. Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives distinctes (chaine simple) dont les deux sommets extrémités sont identiques. Dans les graphes orientés, la notion équivalente est celle de circuit, même si on parle parfois aussi de cycle (par exemple dans l'expression graphe acyclique orienté).
Component (graph theory)
In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components. The number of components in a given graph is an important graph invariant, and is closely related to invariants of matroids, topological spaces, and matrices.