Structures ordonnées
Cours de base (30 h de cours, 30h de TD)
Cours : Éric Thierry (Eric.Thierry)
TD : Laurent Lyaudet (Laurent.Lyaudet)
-
Représentation des ordres. Fermeture et réduction
transitives. Détection de circuits. Hauteur. Extensions
linéaires. Nombres de sauts et dimension.
- Partition minimale en chaînes d'un ordre. Théorème
de Dilworth. Largeur d'un ordre et calcul du antichaîne de
cardinal minimum.
- Caractérisation et reconnaissance de classes d'ordres :
ordres série-parallèles, ordres d'intervalles et ordres
de dimension 2.
- Treillis et treillis distributifs. Construction de treillis
associés à un ordre : treillis des idéaux, treillis des
antichaînes maximales, complété de Mac Neille.
- Treillis de concepts.
- Graphes de comparabilité. Classes de forçage.
Orientations. Invariants de comparabilité.
Bibliographie
B.A. Davey, H.A. Priestley, “Introduction to lattices and
order”, Cambridge University Press, 1991.
M.C. Golumbic, Algorithmic graph theory and perfect graphs,
Academic Press, New-York, 1980.
H. Barbut, B. Monjarjet, Ordres et classification : algbre et
combinatoire, 2 tomes, Hachette université, 1970.