La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

3ème Cours Cours MPRI 2010–2011

De
54 pages
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 ...
Voir plus Voir moins
3`emeCours
Cours MPRI 2010–2011
3e`meCours Cours MPRI 2010–2011
Michel Habib habib@liafa.jussieu.fr http://www.liafa.jussieu.fr/~habib
Chevaleret, septembre 2010
3e`meCoursCoursMPRI20102011
Schedule
Answer to one exercice
Representation of chordal graphs
More structural insights of chordal graphs
Properties of reduced clique graphs
Interval graphs
Exercises
3eme Cours Cours MPRI 2010–2011 ` Answer to one exercice
Helly Property
D´enition A subset family{Ti}iIsatisfies Helly property if JIeti,jJ TiTj6=impliesiJTi6=
Exercise Subtrees in a tree satisfy Helly property.
3`me Cours Cours MPRI 2010–2011 e Answer to one exercice
De´monstration. Suppose not. Consider a family of subtrees that pairwise intersect. For each vertexxof the treeT, it exists at least one subtree of the family totally contained in one connected component ofTx. Direct exactly one edge ofTfromxto this part. We obtain a directed graphG, which has exactlynvertices andn directed edges. SinceTis a tree, it contains no cycle, therefore it must exist a pair of symmetric edges inG, which contradicts the pairwise intersection.
3`emenACsowuerrsotCoounreseMexPcrRiIec02012101
An operation research problem
IStorage of products in fridges : each product is given with an interval of admissible temperatures. Find the minimum number of fridges needed to store all the products (a fridge is at a given temperature). IA solution is given by computing a minimum partition into maximal cliques. IFortunately for an interval graph, this can be polynomially computed ISoknowingthat a graph is an interval graph can help to solve a problem.
3e`meCoursCoursMPRI20102011 Answer to one exercice
Back to chordal graphs
Chordal graph recognition
1.Apply a LexBFS on GO(n+m)
2.the reverse ordering is a simplicial elimination schemeCheck if O(n+m)
3.In case of failure, exhibit a certificate : i.e. a cycle of length 4, without a chord.O(n)
3e`meCoursCoursMPRI20102011 Answer to one exercice
Playing with the representation
Exercise : Find a minimum Coloring (resp. a clique interval graph inO(n) using the interval representation.
of
maximum
size)
of
an
3e`meCours
Cours MPRI 2010–2011
Representation of
Answer
chordal graphs
to
one
exercice
3`emeCoursCoursMPRI20102011 Representation of chordal graphs
About
I
I
I
I
Representations
Interval graphs are chordal graphs
How can we represent chordal graphs ?
As an intersection of some family ?
This family must generalize intervals on
a
line
3`emeCoursCoursMPRI20102011 Representation of chordal graphs
Which
I
I
I
kind of representation ?
Easy to manipulate (optimal encoding, easy algorithms optimisation problems)
Geometric in a wide meaning
Examples : disks in the plane, circular genomes . . .
for
drlacfohoiontntarese1Rep2012010hsapgrsruoIRPMoCemCsru`e3
First remark
Proposition Every undirected graph can be obtained as the intersection of a subset family
Proof G= (V,E) Let us denote byEx={eE|ex6=∅}the set of edges adjacent tox. xyEiffExEy6=We could also have taken the setCxof all maximal cliques which containsxutpeOn.xa`reicossaissuaesclblednsem,lesqieu maximales qui contiennent x CxCy6=iffone maximal clique containing bothxandy
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin