Un graphe orienté sans cycle (en anglais Directed Acyclic Graph) est noté dans la suite par les lettres DAG.
Voici un DAG à 6 sommets :
Cette représentation montre qu'il est naturel de
mettre dans l'ordre F,A,E,D,C,B
(de
haut en bas) les sommets du DAG (il s'agit de ce qu'on
appelle ordre topologique).
D'où la définition suivante :
La relation ≺ entre sommets d'un DAG, définie récursivement par
est dite relation d'ordre sur l'ensemble des sommets du DAG.
S'il y a un arc R→S on dit que R est le prédécesseur immédiat de S, ou que S est le successeur immédiat de R.
Si R≺S on dit que R est un prédécesseur de S ou que S est un successeur de R.
L'ensemble des sommets d'un DAG est dit ordonné.
Sur les sommets d'un DAG, la relation ≺ définit un nouveau DAG appelé clôture transitive du DAG.
Un DAG | sa clôture transitive |
---|---|
Par exemple, puisque dans le DAG initial il y a A→E et E→C, on a A≺E et E≺C donc par transitivité, A≺C. On rajoute donc l'arc A→C ainsi que tous les arcs similaires (de telle manière que tous les successeurs soient immédiats).
On peut alors définir un ensemble ordonné comme un graphe orienté qui est transitivement clos.
Une clôture transitive est difficile à lire à
cause de l'abondance d'arcs (s'il y a n
sommets, il y a n(n-1)/2
arcs) et certains
n'apportent pas d'information. Par exemple l'arc A→C
est superflu puisqu'il y a déjà les arcs A→E et
E→C. On convient alors de ne garder que les arcs
qui sont vraiment nécessaires pour représenter la
relation d'ordre. Autrement dit, on ne considère que les
prédécesseurs et successeurs immédiats.
Le graphe obtenu en en conservant que les prédécesseurs et successeurs immédiats d'une relation d'ordre s'appelle son diagramme de Hasse.
Par exemple le graphe de Hasse de la relation d'ordre ci-dessus est F→A→E→D→C→B. Un diagramme de Hasse n'est pas nécessairement aussi simple que cela.
Le nombre 210 a 16 diviseurs, sur lesquels on peut tracer ce DAG :
Ce DAG est le diagramme de Hasse d'une relation d'ordre,
la divisibilité. Cela signifie que a≺b
(autrement dit, il y a un chemin de a vers b) lorsque
b est divisible par a. En C on écrit
!(b%a)
.
Il s'agit d'une relation d'ordre partiel : par exemple parmi 10 et 15, aucun ne divise l'autre.
Un élément M d'un ensemble ordonné E est dit maximal si pour tout élément x∈E, on a x≺M. Par exemple avec les diviseurs de 120
120 est le maximum de l'ensemble. Le maximum de {2,3,6} est 6 (tous les trois sont des diviseurs de 6). Mais l'ensemble {2,3,5} n'a pas de maximum : aucun de ces trois entiers n'est divisible par tous les autres.
Un élément m d'un ensemble ordonné E est dit minimal si, pour tout élément x∈E, m≺x.
Le minimum des diviseurs de 120 est 1 (qui divise tous les autres). Le minimum de {2,4,12} est 2. Mais {12,24,30,60,120} n'a pas de minimum :
En particulier {12,30} n'a pas de minimum. Par contre il a une borne inférieure.
Une partie d'un ensemble ordonné n'a pas forcément un maximum, mais elle a une borne supérieure : c'est le plus petit élément qui soit plus grand que la partie. Pour la divisibilité, la borne supérieure de deux nombres est leur ppcm noté ∨.
De même la borne inférieure d'une partie est le plus grand élement de l'ensemble qui soit soit inférieur ou égal à tous les éléments de la partie. Par exemple pour la divisibilité, la borne inférieure de deux nombres est leur pgcd noté ∧.
En logique propositionnelle, la relation d'ordre partiel est l'implication notée →, la borne supérieure de deux propositions est leur disjonction également notée ∨ et la borne inférieure de deux propositions est leur conjonction également notée ∧.
Une chaîne d'un ensemble ordonné est un sous-graphe linéaire de son graphe de Hasse. Autrement dit, ce sont des éléments ordonnés dans l'ordre croissant, c'est-à-dire que chacun est inférieur au suivant.
Parmi les diviseurs de 120, on trouve, entre autres, la chaîne
La chaîne 1→3→6 admet un maximum 6, mais a-t-elle une borne supérieure ? Pour le voir, on la replace dans le graphe de Hasse :
En jaune, la chaîne, et en cyan, les éléments qui sont successeurs de 6 (donc de la chaîne). On a vu précédemment que l'ensemble des sommets cyan n'a pas de minimum, mais si on considère la relation de divisibilité comme un ordre large et non strict (6 est un multiple de 6), alors 6 est à la fois borne supérieure et maximum de la chaîne :
En fait toute chaîne de diviseurs parmi les diviseurs de 120 admet une borne supérieure.
On peut jouer à un jeu de type Nim sur un graphe de Hasse. Par exemple avec les diviseurs de 120 :
La version « qui perd gagne » semble plus intéressante, surtout si on se cantonne aux diviseurs de 120.
Lorsque toute chaîne admet une borne supérieure, on dit que l'ensemble ordonné est inductif.
Une relation d'ordre est dite bien fondée si elle n'a aucune chaîne décroissante infinie. C'est par exemple le cas pour la divisibilité sur N* (toute chaîne décroissante s'arrête à 1) et pour la relation d'ordre < sur N.
On considère les deux ensembles ordonnés 1<2<3 et a≺b. Leur produit cartésien est formé des couples (1,a), (1,b), (2,a), (2,b), (3,a) et (3,b). On peut définir plusieurs relations d'ordre sur cet ensemble.
On pose (u,v)ᗉ(x,y) si et seulement si u<x et v≺y on a un ordre dit produit dont voici le diagramme de Hasse :
Bien que < et ≺ soient des ordres totaux, leur produit ᗉ est un ordre partiel. Par exemple entre (1,b) et (2,a) aucun n'est plus petit que l'autre.
En posant (u,v)ᗕ(x,y) si et seulement si
on définit un ordre total sur les 6 couples, dont voici le diagramme de Hasse :
Cet ordre s'appelle lexicographique parce que c'est celui dans lequel les mots sont rangés dans un dictionnaire (ou lexique).
Dans la théorie de la synchronisation des fils d'exécution, on utilise la relation arrivé-avant. C'est une relation d'ordre partiel.
D'ailleurs c'est l'ordre lexicographique sur les
couples (numéro d'attente, priorité)
qui est à la base de l'algorithme de Lamport
(ou de la boulangerie).