Relations d'ordre

I/ Transitivité

1) DAG

Un graphe orienté sans cycle (en anglais Directed Acyclic Graph) est noté dans la suite par les lettres DAG.

Voici un DAG à 6 sommets :

%3 A A B B A->B E E A->E C C C->B D D D->C E->B E->C E->D F F F->A F->D F->E

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 :

2) Relation d'ordre

Définitions

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.

3) Clotûre transitive

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
%3 A A B B A->B E E A->E C C C->B D D D->C E->B E->C E->D F F F->A F->D F->E %3 A A B B A->B C C A->C D D A->D E E A->E C->B D->B D->C E->B E->C E->D F F F->A F->B F->C F->D F->E

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.

II/ Divisibilité

1) Diagramme de Hasse

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.

2) Relation de divisibilité

Le nombre 210 a 16 diviseurs, sur lesquels on peut tracer ce DAG :

%3 1 1 2 2 1->2 3 3 1->3 5 5 1->5 7 7 1->7 6 6 2->6 10 10 2->10 14 14 2->14 3->6 15 15 3->15 21 21 3->21 5->10 5->15 35 35 5->35 7->14 7->21 7->35 30 30 6->30 42 42 6->42 10->30 70 70 10->70 14->42 14->70 15->30 105 105 15->105 21->42 21->105 35->70 35->105 210 210 30->210 42->210 70->210 105->210

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.

3) Minimum et maximum

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

%3 1 1 2 2 1->2 3 3 1->3 5 5 1->5 4 4 2->4 6 6 2->6 10 10 2->10 3->6 15 15 3->15 5->10 5->15 8 8 4->8 12 12 4->12 20 20 4->20 6->12 30 30 6->30 10->20 10->30 15->30 24 24 8->24 40 40 8->40 12->24 60 60 12->60 20->40 20->60 30->60 120 120 24->120 40->120 60->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 :

%3 12 12 24 24 12->24 60 60 12->60 120 120 24->120 60->120 30 30 30->60

En particulier {12,30} n'a pas de minimum. Par contre il a une borne inférieure.

4) Bornes inférieure et supé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 ∧.

III/ Chaînes

1) Chaîne

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

%3 1 1 3 3 1->3 6 6 3->6

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 :

%3 1 1 2 2 1->2 3 3 1->3 5 5 1->5 4 4 2->4 6 6 2->6 10 10 2->10 3->6 15 15 3->15 5->10 5->15 8 8 4->8 12 12 4->12 20 20 4->20 6->12 30 30 6->30 10->20 10->30 15->30 24 24 8->24 40 40 8->40 12->24 60 60 12->60 20->40 20->60 30->60 120 120 24->120 40->120 60->120

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 :

%3 1 1 3 3 1->3 6 6 3->6 12 12 6->12 30 30 6->30 24 24 12->24 60 60 12->60 30->60 120 120 24->120 60->120

En fait toute chaîne de diviseurs parmi les diviseurs de 120 admet une borne supérieure.

2) Jeu de Nim et diviseurs

On peut jouer à un jeu de type Nim sur un graphe de Hasse. Par exemple avec les diviseurs de 120 :

  1. On part de 1 (valeur initiale du nombre courant)
  2. Chaque joueur à son tour, multiplie le nombre courant, au choix, par 2, par 3 ou par 5
  3. Le premier qui arrive à 120 (ou plus) a gagné.

La version « qui perd gagne » semble plus intéressante, surtout si on se cantonne aux diviseurs de 120.

3) Ensemble inductif

Lorsque toute chaîne admet une borne supérieure, on dit que l'ensemble ordonné est inductif.

4) Ordre bien fondé

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.

IV/ Produit

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.

1) Ordre produit

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 :

%3 1a (1,a) 1b (1,b) 1a->1b 2a (2,a) 1a->2a 2b (2,b) 1b->2b 2a->2b 3a (3,a) 2a->3a 3b (3,b) 2b->3b 3a->3b

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.

2) Ordre lexicographique

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 :

%3 1a (1,a) 1b (1,b) 1a->1b 2a (2,a) 1a->2a 1b->2a 2b (2,b) 1b->2b 2a->2b 3a (3,a) 2a->3a 2b->3a 3b (3,b) 2b->3b 3a->3b

Cet ordre s'appelle lexicographique parce que c'est celui dans lequel les mots sont rangés dans un dictionnaire (ou lexique).

V/ Exemple

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).