3ème Cours Cours MPRI 2010–2011

3eme Cours Cours MPRI 2010{20113eme CoursCours MPRI 2010{2011Michel Habibhabib@liafa.jussieu.frhttp://www.liafa.jussieu.fr/ habib~Chevaleret, septembre 20103eme Cours Cours MPRI 2010{2011ScheduleAnswer to one exerciceRepresentation of chordal graphsMore structural insights of chordal graphsProperties of reduced clique graphsInterval graphsExercises663eme Cours Cours MPRI 2010{2011Answer to one exerciceHelly PropertyDe nitionA subset familyfTg satis es Helly property ifi i2I8J I et8i; j2 J T \ T =; implies\ T =;i j i 2J iExerciseSubtrees in a tree satisfy Helly property.3eme Cours Cours MPRI 2010{2011Answer to one exerciceDemonstration.Suppose not. Consider a family of subtrees that pairwise intersect.For each vertex x of the tree T , it exists at least one subtree of thefamily totally contained in one connected component of T x.Direct exactly one edge of T from x to this part.We obtain a directed graph G , which has exactly n vertices and ndirected edges. Since T is a tree, it contains no cycle, therefore itmust exist a pair of symmetric edges in G , which contradicts thepairwise intersection.3eme Cours Cours MPRI 2010{2011Answer to one exerciceAn operation research problemI Storage of products in fridges : each product is given with aninterval of admissible temperatures.Find the minimum number of fridges needed to store all theproducts (a fridge is at a given temperature).I A solution is given by computing a minimum ...