Morphologie des ensembles ordonnés : répercussions algorithmiques
Institution:
NantesDisciplines:
Directors:
Abstract EN:
This thesis deals with morphologic and algorithmic studies of finite posets. Firstly, we are interested in the notion of St-serie decomposition, that is a generalization of serie decomposition. A St-serie decomposition of an order induces a partition of its elements in three subsets. Two of them, which must be none void, give a suborder decomposable by serie composition, and the last one induces an antichain. This decomposition permits to have an inductive characterization of interval orders. Secondly, we investigate the class of chain dominated orders, those orders have a partitions of its elements in two subsets, one inducing a chain and the other inducing a stable set in their covering graph. Finally, we consider the notion of faithfull extension of an order, that is we study the none embedding of this order into a guest order through the preservation of this characteristic on the extensions of the guest orders.
Abstract FR:
Cette thèse traite de l'étude morphologique et algorithmique des ordres finis. Dans un premier temps, on étudie la notion de St-série décomposition qui induit une famille partitive sur ses éléments constituée de trois sous-ensembles, dont deux, non vides, engendrent un sous-ordre décomposable par composition série, tandis que l'autre ensemble induit une antichaîne. On obtient ainsi une caractérisation inductive des ordres d'intervalles. Dans un second temps, on s'intéresse à la classe des ordres chaîne dominés, i. E. Des ordres admettant une famille partitive constituée de deux ensembles, l'un induisant une chaîne et l'autre induisant un stable dans leur graphe de couverture. Dans un troisième temps, on considère la notion d'extension respectueuse d'un ordre, c'est-à-dire que l'on étudie le non abritement d'un ordre dans un ordre cible à travers la préservation de cette caractéristique sur les extensions de l'ordre cible.