1 Alain Gély - Journée Treillis Lorrain, 2008/12/01 Treillis démantelables & X-hyper-arbres I. Treillis démantelables : Définitions & propriétés II. Hiérarchies,

1Alain Gély - Journée Treillis Lorrain, 2008/12/01

Treillis démantelables & X-hyper-arbres

I. Treillis démantelables : Définitions & propriétés

II. Hiérarchies, quasi-hiérarchies, treillis démantelables

III. Treillis démantelables, hyper-arbres et X-hyper-arbres

Treillis démantelables & X-hyper-arbres

Alain GélyLITA, Université Paul Verlaine, Metz

[email protected]

Journée des Treillis Lorrains Nancy

1er Décembre 2008


PLAN





Treillis démantelables : Définitions & propriétés

J(T) = 1, 2, 3 M(T) = 4, 5, 6 Irr(T) = Ø

0

1 2 3

4 5 6

7

0

1 2

3 4

5

J(T) = 1, 2, 4 M(T) = 1, 3, 4 Irr(T) = 1, 4

Soit un treillis T

J(T) famille des éléments sup-irréductibles de T M(T) famille des éléments inf-irréductibles de T Irr(T) famille des éléments doublement-irréductibles de T



0

1 2

3 4

5

J(L) = 1, 2, 4 M(L) = 1, 3, 4 Irr(L) = 1, 4

0

2

3

5

J(L) = 2, 3, 5 M(L) = 0, 2, 3 Irr(L) = 2, 3

0

5

J(L) = 5 M(L) = 0 Irr(L) = Ø

Ø

Étape 1 Étape 2 Étape 3 Étape 4





coeur (core)



Caractérisation (Rival 74)

Soit T un treillis, les propriétés ci-dessous sont équivalentes

T est démantelable

l(Sub(T)) = |T|

Irr(S) ≠ Ø pour tout sous-treillis S de T

pour toute chaine C de T il existe un entier positif n et une chaine C =S

0 ... S

n = T de sous-treillis de T tq |S

i|=|S

i-1|+1 pour tout

i=1,2,...,n



planaire démantelable démantelable planaire



planaire démantelable démantelable planaire

note : planarité du diagramme de Hasse

note : planarité du diagramme de Hasse



0

1

2

3

4

5

6

7

8

0

1 3 2 45

6

7

8

démantelable ∩ atomique planaire



Peut-on considérer un treillis démantelable comme obtenu à partir de la famille des cliques maximales d'un graphe ?

1 2 3 4

1234

12 23 34

2 3

G



Peut-on considérer un treillis démantelable comme obtenu à partir de la famille des cliques maximales d'un graphe ?

1 2

34

1234

12 23 34

2 3

14

41

12 23 34

2 3

14

41

couronne (crown)

G

D. Kelly, I. Rival, Crowns, fences, and dismantlable lattices, Canad. J. Math. 26. (1974), 1257–1271

Un treillis est démantelable ssi

il ne contient pas de couronne



1

2

3

4 5

12 23 34 45

2 4 5

12345

15

1 3

parallèle graphe cordés / treillis

démantelable

élément simplicial / graphe trivial

élément doublement irréductible/ treillis trivial



1 2 3

4 5

6

124 245 235 456

24 25 45

2 4 5

235

G un graphe triangulé

nécessaire non suffisant



1 2 3

4 5

6

124 245 235 456

24 25 45

2 4 5

235

G un graphe triangulé

nécessaire non suffisant

Intersection vide

Ensembles s'intersectant deux à deux



G graphe triangulé Graphes cliques-helly?



1247 2457 2357 4567

247 257 457

27 47 57

1234567

1 2 3

4 5

6

7

7


PLAN





Hiérarchies, quasi-hiérarchies, treillis démantelables

12 34 56

2 4 5

12345

1 3

{x} F X F

6

F une famille d'ensembles sur X tq

A ∩ B = Ø A B B A

pour A, B F , soit

Hiérarchie



12 23 34 45

2 4 5

12345

1 3

A ∩ B ∩ C {A ∩ B , B ∩ C , A ∩ C}

{x} F X F


Quasi-hiérarchie



12 23 34 45

2 4 5

12345

15

1 3

(1) Quasi-hierarchie treillis démantelable

A ∩ B ∩ C {A ∩ B , B ∩ C , A ∩ C}

{x} F X F

Quasi-hiérarchie




A B C

A∩B

A∩B∩C

A∩C B∩C

(2) treillis démantelable Quasi-hiérarchie

Preuve par la contraposé

A B C

A∩B

A∩C

B∩C

(1) Quasi-hierarchie treillis démantelable



" Main cluster structures dealt with in data analysis range from well-known hierarchies to quasi-hierarchies [14]. Between hierarchies and quasi-hierarchies are pyramids [16]. Between hierarchies and pyramids are 2-3 hierarchies [5] (...) "

Cluster structures and collections of Galois closed entity subsets,Mohammed Benayade, Jean Diatta

Discrete Applied Mathematics 156 (2008) 1295-1307

quasi-hierarchie

hypergraphe d'intervalle

hierarchie

planaire

non-planairedémantelable ∩ atomique ?

(pyramides, pseudo-hiérarchies)

2-3 hiérarchie



" Main cluster structures dealt with in data analysis range from well-known hierarchies to quasi-hierarchies [14]. Between hierarchies and quasi-hierarchies are pyramids [16]. Between hierarchies and pyramids are 2-3 hierarchies [5] (...) "

Cluster structures and collections of Galois closed entity subsets,Mohammed Benayade, Jean Diatta

Discrete Applied Mathematics 156 (2008) 1295-1307

quasi-hierarchie

hypergraphe d'intervalle

hierarchies

démantelable ∩ atomique ? X-hyper-arbres?


PLAN





Treillis démantelables, hyper-arbres et X-hyper-arbres

démantelable ∩ atomique quasi-ultramétriques cordées / X-hyperarbres

Question : Y-a-t-il un lien entre les X-hyperarbres et les treillis atomiques démantelables (t.a.d) ?

?

Réponse :X-hyperarbres et t.a.d

sont équivalents



Caractérisation : Un hypergraphe H = (X,E) est un hyper-arbre ssi les deux conditions suivantes sont vérifiées :

Le graphe d'intersection de H est cordé La propriété de Helly doit être vérifiée pour H

duchet 1978

( la fermeture par intersection d'un hyper-arbre est un hyper-arbre )

X = {a,b,c,d,e}E = {ade, abe, bce, cde}

ade

bce

abecde



X-hyper-arbre : Un X-hyper-arbre est un hyper-arbre H=(X,E) tel que toute restriction H'=(Y,E), Y X soit un hyperarbre

exemple

X = {a,b,c}E = {a, ab, ac, b}

ab

ac

ba

c

b

X = {a,b,c}E = {a, ab, ac, b}

ab

ba

X = {a,b,c}E = {a, ab, ac, b}

ac

a

X = {a,b,c}E = {a, ab, ac, b}



Exemple : hyper-arbre dont la restriction n'est pas un hyper-arbre

X = {a,b,c,d,e}E = {ade, abe, bce, cde}

ade

bce

abecde

Y = {a,b,c,d,e}E = {ade, abe, bce, cde}

ad

bc

abcd



Soit F un système de fermeture,

mq si (F , ) est démantelable, alors F est un X-hyper-arbre

F est un hyper-arbre, en effet :

(1) Soient A,B,C F, A ∩ B ∩ C {A ∩ B , B ∩ C , A ∩ C} (quasi-hierarchie) propriété de Helly

(2) Supposons le graphe d'intersection de F non cordé

A1

A2

Ai

A1

A2 A

i Contradiction

Preuve (1/3)





mq toute restriction de F est un hyper-arbre :

La restriction d'un système de fermeture est un système de fermeture

xA xB

xA∩B

Toute restriction (F' , ) de (F , ) démantelable est démantelable

xA B

A∩B

cas 1 cas 2

Preuve (2/3)





A B

A∩B

Toute restriction (F' , ) de (F , ) démantelable est démantelableSupposons le contraire

B∩C C∩D D∩A

C D

présence d'une couronne pour (F' , ) sur X \ {x}

présence d'une couronne pour (F , ) sur X : contradiction

Preuve (3/3)



Réciproquement, Soit F un système de fermeture,

mq si F est un X-hyper-arbre, alors (F , ) est démantelable

contraposé : si (F , ) n'est pas démantelable alors F n'est pas un X-hyper-arbre,

A1

A2

Ai

x1

x2

xn

restriction de X à { x1 , x

2 , ... , x

n }

graphe d'intersection non cordéil existe une restriction qui n'est pas un hyper-arbreF n'est pas un X-hyper-arbre

Preuve (1/1)


CONCLUSION


F est un X-hyper-arbre

(F , ) est démantelable

Conclusion

Application à la classification (cf. exposé François Brucker)

A suivre...

Merci.

Documents

1 Alain Gély - Journée Treillis Lorrain, 2008/12/01 Treillis démantelables & X-hyper-arbres I. Treillis démantelables : Définitions & propriétés II. Hiérarchies,