Chapitre 1 • Structures ordonnées Applications des treillis
6
Pour obte nir la repré sen ta tion de la rela tion d’ordre strict cor res pon dant à | (divise),
c’est àdire la rela tion (divise et n’est pas égal), il suf fit de sup pri mer la dia go nale du
tableau 1.7 et les boucles (arcs fer més sur eux mêmes) de la fig. 1.1. Ici, l’ordre strict
n’est que par tiel (tout comme l’ordre large d’où il provient).
À toute rela tion d’ordre a (ou a) cor res pond une rela tion converse s (ou s).
Le diagramme de Hasse (fig 1.2) s’obtient en supprimant dans la fig. 1.1, les
boucles et les arcs de transitivité : ainsi 1 divise 2 et 2 divise 10 entraîne 1 divise 10 :
l’arc (1,10) est un arc de transitivité.
1.1.3 Élé ments par ti cu liers d’un ensemble ordonné
Un ensemble sur lequel est défi nie une rela tion d’ordre (par tiel ou total) est nommé
ensemble ordonné (par tiel le ment ou tota le ment).
Cer tains élé ments par ti cu liers des ensembles par tiel le ment ordon nés jouent un
grand rôle en recherche opé ra tion nelle.
Consi dé rons un ensemble X, par tiel le ment ordonné par la rela tion a (être infé rieur
ou égal à) et une par tie P de cet ensemble. S’il existe (bien noter cette res tric tion) :
a) Un élé ment m de X qui est infé rieur ou égal à tout élé ment x de P, m est un
mino rant de P.
Un élé ment M de X qui est supé rieur ou égal à tout éle ment x de P, est un majo
rant de P.
b) Un élé ment M de P, tel qu’il n’existe pas d’élé ments de Ρ supé rieur à M, est un
élé ment maximal de P.
1
Un élé ment m de P, tel qu’il n’existe pas d’élé ments de Ρ infé rieur à M, est un
élé ment mini mal de P.
De même les élé ments définis cidessous peuvent exister ou ne pas exister :
c) Le plus grand élé ment E (ou encore : le maxi mum) de P est l’élé ment de P, tel
que, pour tout xPP, on a : E s x.
Le plus petit élé ment e (ou encore : le mini mum) de P est l’élé ment de P, tel que,
pour tout xPP, on a : e a x.
d) La borne supé rieure (b.s.) B de P (ou supremum de P, notée aussi sup P) est le
plus petit élé ment de l’ensemble des majo rants de P.
La borne infé rieure (b.i.) b de P (ou infimum de P, notée aussi inf P) est le plus
grand élé ment de l’ensemble des minorants de P.
e) L’élé mentuni ver sel de X est le plus grand élé ment de X.
L’élé ment nul de X est le plus petit élé ment de X.
1. L’Aca dé mie des sciences recom mande d’employer les termes « maxi mum, mini mum, opti
mum » uni que ment comme subs tan tifs ; les adjec tifs cor res pon dants étant « maximal, mini mal,
opti mal ». Ainsi on doit dire « élé ment maximal » (et non pas « élé ment maxi mum »).
6
Pour obte nir la repré sen ta tion de la rela tion d’ordre strict cor res pon dant à | (divise),
c’est àdire la rela tion (divise et n’est pas égal), il suf fit de sup pri mer la dia go nale du
tableau 1.7 et les boucles (arcs fer més sur eux mêmes) de la fig. 1.1. Ici, l’ordre strict
n’est que par tiel (tout comme l’ordre large d’où il provient).
À toute rela tion d’ordre a (ou a) cor res pond une rela tion converse s (ou s).
Le diagramme de Hasse (fig 1.2) s’obtient en supprimant dans la fig. 1.1, les
boucles et les arcs de transitivité : ainsi 1 divise 2 et 2 divise 10 entraîne 1 divise 10 :
l’arc (1,10) est un arc de transitivité.
1.1.3 Élé ments par ti cu liers d’un ensemble ordonné
Un ensemble sur lequel est défi nie une rela tion d’ordre (par tiel ou total) est nommé
ensemble ordonné (par tiel le ment ou tota le ment).
Cer tains élé ments par ti cu liers des ensembles par tiel le ment ordon nés jouent un
grand rôle en recherche opé ra tion nelle.
Consi dé rons un ensemble X, par tiel le ment ordonné par la rela tion a (être infé rieur
ou égal à) et une par tie P de cet ensemble. S’il existe (bien noter cette res tric tion) :
a) Un élé ment m de X qui est infé rieur ou égal à tout élé ment x de P, m est un
mino rant de P.
Un élé ment M de X qui est supé rieur ou égal à tout éle ment x de P, est un majo
rant de P.
b) Un élé ment M de P, tel qu’il n’existe pas d’élé ments de Ρ supé rieur à M, est un
élé ment maximal de P.
1
Un élé ment m de P, tel qu’il n’existe pas d’élé ments de Ρ infé rieur à M, est un
élé ment mini mal de P.
De même les élé ments définis cidessous peuvent exister ou ne pas exister :
c) Le plus grand élé ment E (ou encore : le maxi mum) de P est l’élé ment de P, tel
que, pour tout xPP, on a : E s x.
Le plus petit élé ment e (ou encore : le mini mum) de P est l’élé ment de P, tel que,
pour tout xPP, on a : e a x.
d) La borne supé rieure (b.s.) B de P (ou supremum de P, notée aussi sup P) est le
plus petit élé ment de l’ensemble des majo rants de P.
La borne infé rieure (b.i.) b de P (ou infimum de P, notée aussi inf P) est le plus
grand élé ment de l’ensemble des minorants de P.
e) L’élé mentuni ver sel de X est le plus grand élé ment de X.
L’élé ment nul de X est le plus petit élé ment de X.
1. L’Aca dé mie des sciences recom mande d’employer les termes « maxi mum, mini mum, opti
mum » uni que ment comme subs tan tifs ; les adjec tifs cor res pon dants étant « maximal, mini mal,
opti mal ». Ainsi on doit dire « élé ment maximal » (et non pas « élé ment maxi mum »).