3.3 Algorithme de génération de treillis
quelconques
Dans cette section, nous présenterons un algorithme
permettant de vérifier si un graphe orienté sans circuit
represente un treillis. Mais avant cela, nous vous présentons quelques
définitions qui seront utilisées par la suite.
Soit X un ensemble fini et = une relation d'ordre
définie sur X ; (i.e refléxive,
antisymétrique et transitive). On note par P = (X,
=P) un ensemble sur lequel on a défini un ordre.
Alors:
- Deux éléments x et y de
X sont dits comparables si x =P y
ou y =P x, sinon ils sont dits
incomparables.
- Un ordre total ou chaîne est un ensemble d'
éléments deux à deux comparables.
- Q = (X, =Q) est une
extension de P = (X, =P) si x
=P y = x =Q y
pour tout x,y ? X.
- Un ordre total L = (X,
=L) est une extension lineaire de P = (X,
=P) si L est une extension de P.
- Un ensemble A muni de deux lois + et * est
appelé anneau si :
1. (A, +) est un groupe Abélien;
2. La loi * est associative;
36
3. La loi * est distributive par rapport à la loi
+
Si de plus, la loi interne * est commutative alors l'anneau
sera dit commutatif.
- Soit A un anneau commutatif. un sous ensemble S
c A est un idéal si :
1. a + a' E S pour tout a, a' E S
;
2. r.a E S pour tout a E S
et r E A
En d'autres termes, un "Idéal" est un sous ensemble
fermé pour l'addition et stable pour la multiplication par un
élément quelconque de A
- Un Idéal I d'un ordre
P, est une Partie héréditaire supérieure
ou filtre ; c'est-à-dire I C X
tel que si y E I et x E X
vérifient x <P y alors x E
I[50]
Propriété 1 Soit T = (X, <)
un treillis et x E X. Si a < b
alors a V x < b V x. Preuve
Soientz,tEX,z<zVtett<tVz.Puisquea<bonaaVb=bet
(xVa)Vb=xVbparconséquent:xVa<xVb.
Soit ô = x1, x2,
...xn une extension linéaire de G. Pour tout
k E [1, n] il vient que Yk-1 = xk-1,
..., xn est un filtre. Ainsi l'algorithme devra vérifier
si Yk-1 est un sup-demi-treillis pour k
variant de n à 2 ; il se base sur le lemme
suivant :
Lemme 1 Soit G = (X, U) un graphe
orienté sans circuit et Yk-1 = xk-1, ...,
xn tel que tout couple d'éléments de
Yk-1 admet une borne supérieure.
Alors pour tout z E Yk-1, xk
V z existe, si et seulement si y V z tel que
y E ImmSucc(xk) admet un élément minimal w
= y V z.
Preuve Si pour z E
Yk-1, xk V z existe, alors pour tout
y E ImmSucc(xk) on a : xk V y > xk
V z.
Puisque xk V z > xk, alors il
existe t0 < xk. De ce qui précède, on en
déduit que xk V z > z et donc xk
V z > t0 V z.
Si pour z E Yk-1 il existe
t0 E ImmSucc(xk) tel que w = t0 V z, soit
un élément minimal de y V z tel que y
E ImmSucc(xk) alors w > z et w >
xk
Soit v E X tel que v > z
et v > xk. Alors v E
Yk-1 et il existe t0 E ImmSucc(xk) tel
que v > t0 et puisque v > t0 V z
> w > xk V z, il vient alors que w =
xk V z.[6]
3.3.1 Algorithme de L.Nourine
L'algorithme de Lhouari Nourine reconnait si un graphe G =
(X, U) est le graphe
de couverture d'un treillis.[5]
Algorithme Reconnaissance d'un treillis.
Donnée : La reduction transitive d'un
graphe sans circuits G = (X, U), donnée par
sa liste d'adjacence de prédécesseurs.
Résultat : G est-il le graphe de
couverture d'un treillis ?
Début
// Calculer une extension linéaire ô =
x1, x2, ...xn de G
Y = (xn) est un sup-demi-treillis.
Pour i = n - 1,2
faire
le calcul des bornes supérieurs entre xi et ses
successeurs.
Pour y E]xi, xn]
faire
xi V y = y ;
marquer y.
Fin pour
// Calcul des bornes supérieures entre xi et les
elements qui lui sont incomparables.
Pour j = n, i + 1
faire
37
FIGURE 3.6 - Un ordre qui ne représente pas un
treillis
Si x est non marqué
alors
x est incomparable à xi
Si w = min(xi ? z) tel que
z ? ImmSucc(xi) existe alors
xi ? x = w.
Sinon
G n'est pas la graphe de couverture d'un treillis.
Fin si
Fin si
Fin pour
Fin pour
Fin
| 
