1.1 Notions sur les struc tures ordonnées
© Dunod – Toute reproduction non autorisée est un délit.
5
On véri fie aisé ment sur le tableau la réflexi vité et l’anti symé trie. On vérifie (moins
faci le ment) la tran si ti vité sur ce tableau par les “rectangles” dont un des sommets est
sur la diagonale :
(1, 2) . . . (1, 10) (1, 10) . . . (1, 30)
(1, 3) . . . (1, 30)
(2, 2) . . . (2, 10) (10, 10) . . . (10, 30)
(3, 3) . . . (3, 30)
(1, 2) . . . (1, 30) (5, 10) . . . (2, 30)
(1, 5) . . . (1, 20)
(2, 2) . . . (2, 30) (10, 10) . . . (10, 30)
(5, 5) . . . (5, 20)
(1, 5) . . . (1, 10) (5, 10) . . . (5, 30) (1, 10) . . . (1, 20)
(5, 5) . . . (5, 10) (10, 10) . . . (10, 30) (10, 10) . . . (10, 20)
(1, 5) . . . (1, 30)
(1, 2) . . . (1, 20) (2, 10) . . . (2, 20)
(5, 5) . . . (5, 30)
(2, 2) . . . (2, 20) (10, 10) . . . (10, 20)
(5, 10) . . . (5, 20)
(10, 10) . . . (10, 20)
Ainsi le rectangle en haut à gauche se lit : 1/2 et 2/2 et
2/10 entraîne 1/10.
Contrai re ment à ce qui se passe pour le
tableau 1.5, la par tie supé rieure du tableau
(au- dessus de la dia go nale) ne fait pas appa -
raître tous les couples. C’est qu’au sens de la
rela tion tous les élé ments ne sont pas deux
à deux compa rables. Ainsi, par exemple, on
n’a pas 2 | 3 ni 2 | 5 (et pas davan tage 3 | 2
ou 5 | 2).
On exprime ce fait en disant que l’ordre
est par tiel. Dans le cas contraire, l’ordre est total. La rela tion < sur N, Z, Q ou R
(ou tout sous- ensemble de ceux- ci) est une rela tion d’ordre total. On peut don ner une
repré sen ta tion « sagit tale » de la rela tion (figure 1.1) :
Deux élé ments a et b, repré sen tés cha cun par un point, sont réunis par
un arc si et seule ment si a | b. Il y a autant d’arcs que de couples dans le
tableau 1.7 soit 22, y compris 7 boucles. Mais on peut réduire le nombre de
ces arcs, en sup pri mant ceux qui résultent de la réflexi vité et de la tran si ti
vité. On obtient alors un dia gramme de Hasse (fig. 1.2), plus lisible.
Le dia gramme de Hasse d’un ensemble tota le ment ordonné est une
chaîne (fig. 1.3) (en fait, en termes de graphes orien tés, il s’agira d’un
che min).
À toute rela tion d’ordre large cor res pond une et une seule rela tion d’ordre strict.
Une rela tion d’ordre strict est ir réflexive,asy mé trique et tran si tive. Elle peut induire
un ordre par tiel ou un ordre total.
Figure 1.1
Figure 1.2
Figure 1.3
© Dunod – Toute reproduction non autorisée est un délit.
5
On véri fie aisé ment sur le tableau la réflexi vité et l’anti symé trie. On vérifie (moins
faci le ment) la tran si ti vité sur ce tableau par les “rectangles” dont un des sommets est
sur la diagonale :
(1, 2) . . . (1, 10) (1, 10) . . . (1, 30)
(1, 3) . . . (1, 30)
(2, 2) . . . (2, 10) (10, 10) . . . (10, 30)
(3, 3) . . . (3, 30)
(1, 2) . . . (1, 30) (5, 10) . . . (2, 30)
(1, 5) . . . (1, 20)
(2, 2) . . . (2, 30) (10, 10) . . . (10, 30)
(5, 5) . . . (5, 20)
(1, 5) . . . (1, 10) (5, 10) . . . (5, 30) (1, 10) . . . (1, 20)
(5, 5) . . . (5, 10) (10, 10) . . . (10, 30) (10, 10) . . . (10, 20)
(1, 5) . . . (1, 30)
(1, 2) . . . (1, 20) (2, 10) . . . (2, 20)
(5, 5) . . . (5, 30)
(2, 2) . . . (2, 20) (10, 10) . . . (10, 20)
(5, 10) . . . (5, 20)
(10, 10) . . . (10, 20)
Ainsi le rectangle en haut à gauche se lit : 1/2 et 2/2 et
2/10 entraîne 1/10.
Contrai re ment à ce qui se passe pour le
tableau 1.5, la par tie supé rieure du tableau
(au- dessus de la dia go nale) ne fait pas appa -
raître tous les couples. C’est qu’au sens de la
rela tion tous les élé ments ne sont pas deux
à deux compa rables. Ainsi, par exemple, on
n’a pas 2 | 3 ni 2 | 5 (et pas davan tage 3 | 2
ou 5 | 2).
On exprime ce fait en disant que l’ordre
est par tiel. Dans le cas contraire, l’ordre est total. La rela tion < sur N, Z, Q ou R
(ou tout sous- ensemble de ceux- ci) est une rela tion d’ordre total. On peut don ner une
repré sen ta tion « sagit tale » de la rela tion (figure 1.1) :
Deux élé ments a et b, repré sen tés cha cun par un point, sont réunis par
un arc si et seule ment si a | b. Il y a autant d’arcs que de couples dans le
tableau 1.7 soit 22, y compris 7 boucles. Mais on peut réduire le nombre de
ces arcs, en sup pri mant ceux qui résultent de la réflexi vité et de la tran si ti
vité. On obtient alors un dia gramme de Hasse (fig. 1.2), plus lisible.
Le dia gramme de Hasse d’un ensemble tota le ment ordonné est une
chaîne (fig. 1.3) (en fait, en termes de graphes orien tés, il s’agira d’un
che min).
À toute rela tion d’ordre large cor res pond une et une seule rela tion d’ordre strict.
Une rela tion d’ordre strict est ir réflexive,asy mé trique et tran si tive. Elle peut induire
un ordre par tiel ou un ordre total.
Figure 1.1
Figure 1.2
Figure 1.3