Structures ordonnées
Cours de base (30 h de cours, 30h de TD)
Cours : Vincent Bouchitté (Vincent.Bouchitte)
TD : Éric Thierry (Eric.Thierry)
-
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.