Exemple de graphe acyclique orienté En mathématiques , notamment en théorie des graphes , et en informatique , un graphe orienté acyclique ( DAG ) est un graphe orienté sans cyc...
Worldlex WikiFrancaisLecture gratuite
Exemple de graphe acyclique orienté
En mathématiques , notamment en théorie des graphes , et en informatique , un graphe orienté acyclique ( DAG ) est un graphe orienté sans cycle . Autrement dit, il est constitué de sommets et d'arêtes (ou arcs ), chaque arête reliant un sommet à un autre, de sorte que suivre ces directions ne forme jamais de boucle fermée. Un graphe orienté est un DAG si et seulement s'il peut être topologiquement ordonné , c'est-à-dire en arrangeant ses sommets selon un ordre linéaire compatible avec le sens de toutes les arêtes. Les DAG ont de nombreuses applications scientifiques et informatiques, allant de la biologie (évolution, arbres généalogiques, épidémiologie) aux sciences de l'information ( réseaux de citations ) en passant par le calcul ( ordonnancement ).
Les graphes acycliques orientés sont également appelés graphes orientés acycliques ou digraphes acycliques .
Définitions
Un graphe est formé de sommets et d' arêtes reliant deux à deux ces sommets. Les sommets peuvent représenter n'importe quel type d'objet relié deux à deux par des arêtes. Dans le cas d'un graphe orienté , chaque arête possède une orientation, d'un sommet vers un autre. Un parcours dans un graphe orienté est une suite (finie ou infinie) de sommets.
propriétés mathématiques
Relation d'accessibilité, clôture transitive et réduction transitive
Un DAG
Sa réduction transitive
La relation d'accessibilité d'un graphe acyclique orienté (DAG) peut être formalisée par un ordre partiel et si et seulement s'il existe un chemin orienté de dans le DAG ; autrement dit, si (ou si ). Cependant, différents DAG peuvent donner lieu à la même relation d'accessibilité et au même ordre partiel. Par exemple, un DAG avec deux arêtes et a la même relation d'accessibilité qu'un DAG avec trois arêtes , et . Ces deux DAG produisent le même ordre partiel, dans lequel les sommets sont ordonnés .
La fermeture transitive d'un DAG est le graphe possédant le plus grand nombre d'arêtes et ayant la même relation d'accessibilité que le DAG. Elle possède une arête pour chaque paire de sommets ( ) dans la relation d'accessibilité en termes de théorie des graphes. La même méthode de traduction des ordres partiels en DAG s'applique de manière plus générale : pour tout ensemble partiellement ordonné fini , le graphe qui possède un sommet pour chaque élément de est automatiquement un DAG transitivement fermé, et a comme relation d'accessibilité. Ainsi, tout ensemble partiellement ordonné fini peut être représenté par un DAG.
Un diagramme de Hasse représentant l'ordre partiel d'inclusion (⊆) parmi les sous-ensembles d'un ensemble à trois éléments
The transitive reduction of a DAG is the graph with the fewest edges that has the same reachability relation as the DAG. It has an edge for every pair of vertices () in the covering relation of the reachability relation for which the DAG also contains a longer directed path from . Like the transitive closure, the transitive reduction is uniquely defined for DAGs. In contrast, for a directed graph that is not acyclic, there can be more than one minimal subgraph with the same reachability relation. Transitive reductions are useful in visualizing the partial orders they represent, because they have fewer edges than other graphs representing the same orders and therefore lead to simpler graph drawings. A Hasse diagram of a partial order is a drawing of the transitive reduction in which the orientation of every edge is shown by placing the starting vertex of the edge in a lower position than its ending vertex.
Topological ordering
A topological ordering of a directed acyclic graph: every edge goes from earlier in the ordering (upper left) to later in the ordering (lower right). A directed graph is acyclic if and only if it has a topological ordering.
Adding the red edges to the blue directed acyclic graph produces another DAG, the transitive closure of the blue graph. For each red or blue edge u → v, v is reachable from u: there exists a blue path starting at u and ending at v.
L' ordre topologique d'un graphe orienté est un ordre de ses sommets en une séquence telle que, pour chaque arête, son sommet de départ précède son sommet d'arrivée dans la séquence. Un graphe possédant un ordre topologique ne peut contenir de cycle, car l'arête aboutissant au premier sommet d'un cycle serait alors mal orientée. Par conséquent, tout graphe possédant un ordre topologique est acyclique. Réciproquement, tout graphe orienté acyclique possède au moins un ordre topologique. L'existence d'un ordre topologique peut donc servir de définition équivalente des graphes orientés acycliques : ce sont précisément les graphes qui possèdent un ordre topologique. En général, cet ordre n'est pas unique ; un graphe acyclique orienté (DAG) possède un ordre topologique unique si et seulement s'il possède un chemin orienté contenant tous ses sommets, auquel cas l'ordre est le même que l'ordre d'apparition des sommets dans le chemin.
La famille des ordres topologiques d'un DAG est la même que la famille des extensions linéaires de la relation d'accessibilité pour le DAG, donc deux graphes quelconques représentant le même ordre partiel ont le même ensemble d'ordres topologiques.
Eric W. Weisstein a conjecturé , et matrices (0,1) dont toutes les valeurs propres sont des nombres réels positifs . La démonstration est bijective : une matrice + I est une matrice (0,1) dont toutes les valeurs propres sont positives, où préserve la propriété selon laquelle tous les coefficients de la matrice sont égaux à 0 ou 1.
Familles de graphes apparentées
Un multitree , un DAG dans lequel le sous-graphe accessible depuis n'importe quel sommet induit un arbre non orienté (par exemple en rouge)
Un polytree , un DAG formé en orientant les arêtes d'un arbre non orienté
Un multitree (également appelé graphe fortement non ambigu ou mangrove ) est un DAG dans lequel il existe au plus un chemin orienté entre deux sommets quelconques. De manière équivalente, c'est un DAG dans lequel le sous-graphe accessible depuis n'importe quel sommet induit un arbre non orienté .
Un polytree (également appelé arbre orienté ) est un multitree formé en orientant les arêtes d'un arbre non orienté.
Une arborescence est un polyarbre formé en orientant les arêtes d'un arbre non orienté à partir d'un sommet particulier, appelé la racine de l'arborescence.
Dans tous ces algorithmes de fermeture transitive, il est possible de distinguer les paires de sommets accessibles par au moins un chemin de longueur deux de celles qui ne peuvent être reliées que par un chemin de longueur un. La réduction transitive consiste en les arêtes formant les seuls chemins reliant leurs extrémités. Par conséquent, la réduction transitive peut être construite dans les mêmes limites de temps asymptotiques que la fermeture transitive.
Problème de fermeture
Les graphes dont les sommets représentent des événements survenant à un instant précis, et dont les arêtes pointent toujours d'un sommet associé à un instant antérieur vers un sommet associé à un instant postérieur, sont nécessairement orientés et acycliques. L'absence de cycle découle du fait que le temps associé à un sommet augmente systématiquement lorsqu'on parcourt un chemin orienté dans le graphe ; il est donc impossible de revenir à un sommet donné. Ceci reflète notre intuition naturelle selon laquelle la causalité implique que les événements n'affectent que le futur, jamais le passé, et qu'il n'existe donc pas de boucles causales . Un exemple de ce type de graphe orienté acyclique est celui rencontré dans l' approche des ensembles causaux en gravité quantique, bien que dans ce cas, les graphes considérés soient transitivement complets . Dans l'exemple d'historique des versions ci-dessous, chaque version du logiciel est associée à un instant unique, généralement celui de sa sauvegarde, de sa validation ou de sa publication. Dans les exemples de graphes de citations ci-dessous, les documents sont publiés simultanément et ne peuvent faire référence qu'à des documents antérieurs.
Parfois, les événements ne sont pas associés à un instant physique précis. Si les paires d'événements sont liées par une relation purement causale (c'est-à-dire si les arêtes représentent les relations causales entre les événements), on obtient un graphe orienté acyclique . Par exemple, un réseau bayésien représente un système d'événements probabilistes sous forme de sommets dans un graphe orienté acyclique, où la vraisemblance d'un événement peut être calculée à partir des vraisemblances de ses prédécesseurs dans le graphe [38]. , le graphe moral d'un graphe orienté acyclique est le graphe non orienté obtenu en ajoutant une arête (non orientée) entre tous les parents d'un même sommet (opération parfois appelée « mariage » ), puis en remplaçant toutes les arêtes orientées par des arêtes non orientées . Un autre type de graphe présentant une structure causale similaire est le diagramme d'influence , dont les sommets représentent soit des décisions à prendre, soit des informations inconnues, et les arêtes représentent les influences causales d'un sommet à l'autre . En épidémiologie , par exemple, ces diagrammes sont souvent utilisés pour estimer la valeur espérée de différentes options d'intervention.
La réciproque est également vraie. Autrement dit, toute application représentée par un graphe acyclique orienté possède une structure causale, qu'il s'agisse d'un ordre explicite (ou temporel, comme dans l'exemple) ou d'un ordre déductible de la structure du graphe. Ceci s'explique par le fait que tout graphe acyclique orienté possède un ordre topologique : il existe au moins une façon d'ordonner les sommets de sorte que toutes les arêtes soient orientées dans la même direction le long de cet ordre.
Les arbres généalogiques peuvent être considérés comme des graphes orientés acycliques, avec un sommet pour chaque membre de la famille et une arête pour chaque relation parent-enfant. Malgré leur nom, ces graphes ne sont pas nécessairement des arbres, car les mariages entre apparentés (un enfant ayant alors un ancêtre commun du côté maternel et paternel) peuvent entraîner un effondrement de la lignée . Les graphes de descendance matrilinéaire (relations mère-fille) et patrilinéaire (relations père-fils) sont des arbres au sein de ce graphe. Puisqu'une personne ne peut être son propre ancêtre, les arbres généalogiques sont acycliques.
L’historique des versions d’un système de contrôle de versions distribué , tel que Git , présente généralement la structure d’un graphe acyclique orienté, où chaque révision est représentée par un sommet et les paires de révisions directement dérivées l’une de l’autre par une arête. Il ne s’agit généralement pas d’arbres en raison des fusions.
Dans de nombreux algorithmes randomisés de géométrie algorithmique , l'algorithme conserve un graphe acyclique orienté (DAG) d'historique représentant l'historique des versions d'une structure géométrique au cours d'une séquence de modifications. Par exemple, dans un algorithme incrémental randomisé pour la triangulation de Delaunay , la triangulation évolue en remplaçant un triangle par trois triangles plus petits à chaque ajout de point, et par des opérations de « symétrie » qui remplacent des paires de triangles par une paire différente. Le DAG d'historique de cet algorithme possède un sommet pour chaque triangle construit au cours de l'algorithme, et des arêtes reliant chaque triangle aux deux ou trois autres triangles qui le remplacent. Cette structure permet de répondre efficacement aux requêtes de localisation de points : pour trouver la position d'un point . Le triangle final atteint sur ce chemin est nécessairement le triangle de Delaunay contenant
Graphiques de citations
Dans un graphe de citations, les sommets représentent des documents ayant une date de publication unique. Les arêtes représentent les citations de la bibliographie d'un document vers d'autres documents nécessairement antérieurs. L'exemple classique est celui des citations entre articles scientifiques, comme l'ont souligné Derek J. de Solla Price dans son article de 1965 intitulé « Networks of Scientific Papers » qui a ensuite élaboré le premier modèle de réseau de citations, le modèle de Price . Dans ce cas, le nombre de citations d'un article correspond simplement au degré entrant du sommet correspondant dans le réseau de citations. Il s'agit d'une mesure importante en analyse de citations . Les décisions de justice en constituent un autre exemple : les juges étayent leurs conclusions en se référant à des décisions antérieures. Enfin, les brevets en fournissent un dernier exemple, car ils doivent faire référence à l'état de la technique , c'est-à-dire à des brevets antérieurs pertinents pour la revendication du brevet actuel. En tenant compte des propriétés spécifiques des graphes orientés acycliques, il est possible d'analyser les réseaux de citations à l'aide de techniques inaccessibles pour l'analyse des graphes généraux considérés dans de nombreuses études d' analyse de réseaux . Par exemple, la réduction transitive apporte un nouvel éclairage sur les distributions de citations observées dans différentes applications, mettant en évidence des différences nettes dans les mécanismes de création des réseaux de citations selon les contextes. Une autre technique est l'analyse du chemin principal , qui retrace les liens de citation et suggère les chaînes de citations les plus significatives dans un graphe de citations donné .
Le modèle de Price est trop simple pour représenter fidèlement un réseau de citations, mais il est suffisamment simple pour permettre des solutions analytiques pour certaines de ses propriétés. Nombre d'entre elles peuvent être obtenues à partir de résultats dérivés de la version non orientée du modèle de Price , le modèle de Barabási-Albert . Cependant, comme le modèle de Price définit un graphe acyclique orienté, il s'avère utile pour le calcul analytique de propriétés propres aux graphes acycliques orientés. Par exemple, la longueur du plus long chemin, du n-ième nœud ajouté au réseau au premier nœud du réseau, est proportionnelle à
Compression des données
Les graphes acycliques orientés (DAG) peuvent également servir de représentation compacte d'une collection de séquences. Dans ce type d'application, on trouve un DAG dont les chemins forment les séquences données. Lorsque plusieurs séquences partagent les mêmes sous-séquences, ces dernières peuvent être représentées par une partie commune du DAG, ce qui permet d'utiliser moins d'espace que si l'on listait toutes les séquences séparément. Par exemple, le graphe acyclique orienté de mots est une structure de données en informatique, constituée d'un graphe acyclique orienté avec une source unique et dont les arêtes sont étiquetées par des lettres ou des symboles ; les chemins de la source aux puits dans ce graphe représentent un ensemble de chaînes de caractères , telles que des mots anglais. Tout ensemble de séquences peut être représenté par des chemins dans un arbre, en créant un sommet pour chaque préfixe d'une séquence et en faisant en sorte que le parent de l'un de ces sommets représente la séquence à laquelle il manque un élément ; l'arbre ainsi formé pour un ensemble de chaînes de caractères est appelé un trie .
De même, un arbre binaire de recherche peut être vu comme un DAG enraciné où les chemins représentent des ordres triés de clés, bien qu'il ne bénéficie pas de la compression par fusion de chemins présente dans les DAG plus complexes. Un graphe de mots acyclique orienté permet de gagner de l'espace par rapport à un trie en autorisant les chemins à diverger et à se rejoindre, de sorte qu'un ensemble de mots ayant les mêmes suffixes possibles peut être représenté par un seul sommet de l'arbre.
Worldlex Wiki 
