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

Partagez cette publication

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