Nous traitons d'abord le problème consistant à placer sur une droite les sommets d'un hypergraphe partiellement ordonné de fa?on à minimiser le nombre de ruptures dans la représentation des arêtes de cet hypergraphe. Nous présentons deux applications : l'une concerne la programmation linéaire entière et l'autre un problème d'ordonnancement. Dans la deuxième partie de ce travail, nous caractérisons les graphes d'intervalles dont les arêtes sont orientées de fa?on à représenter des relations d'inclusion, de recouvrement et d'antériorité.%We first deal with the problem which consists in finding a linear ordering of the vertices of a partially ordered hypergraph H in a way which minimizes the number of "breaks" in the edges of H. We present two applications of this problem: the first one is related with scheduling and the second one has to see with integer linear programming. In the second part of this paper, we characterize interval graphs whose edges are oriented in order to represent inclusion, overlapping and anteriority relationships.
展开▼
