3ème Cours Cours MPRI 2010–2011

Michel Habib [e-mail] ` `%%%`#`&12_`__~~~ Alse

Description

3eme Cours Cours MPRI 2010{20113eme CoursCours MPRI 2010{2011Michel [e-mail]://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 ...

Informations

• Publié par: Zowyong
• Nombre de lectures: 27
• Langue: English

Extrait

3`emeCours

Cours MPRI 2010–2011

3e`meCours Cours MPRI 2010–2011

Michel Habib [e-mail] http://www.liafa.jussieu.fr/ ~ habib

Chevaleret, septembre 2010

3e`meCoursCoursMPRI2010–2011

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´efinition A subset family{T i } i∈I satisfies Helly property if ∀J⊆Iet∀i,j∈J T i ∩T j 6=∅implies∩ i∈J T i 6=∅

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 ofT−x. 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`eme nA C s o w u e r r s ot Co o u n r e s e M ex P cr R i I ec 02012–101

An operation research problem

I Storage 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). I A solution is given by computing a minimum partition into maximal cliques. I Fortunately for an interval graph, this can be polynomially computed I Soknowingthat a graph is an interval graph can help to solve a problem.

3e`meCoursCoursMPRI2010–2011 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`meCoursCoursMPRI2010–2011 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`emeCoursCoursMPRI2010–2011 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`emeCoursCoursMPRI2010–2011 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

drlacfohoiontntarese 1 Rep –2012010 hsapgr sruoIRPMoCemCsru`e3

First remark

Proposition Every undirected graph can be obtained as the intersection of a subset family

Proof G= (V,E) Let us denote byE x ={e∈E|e∩x6=∅}the set of edges adjacent tox. xy∈EiffE x ∩E y 6=∅ We could also have taken the setC x of all maximal cliques which containsxutpeOn.xa`reicossaissuaesclblednsem,l’esqieu maximales qui contiennent x C x ∩C y 6=∅iff∃one maximal clique containing bothxandy