Algorithmes Combinatoires Decomposition en coupes familles bipartitives

Christophe Paul

Description

Algorithmes Combinatoires (2) Decomposition en coupes - familles bipartitives Christophe PAUL (CNRS - LIRMM) November 19, 2009

• famille bipartitive


• graphes de cercles decomposition en coupe des graphes de cercle


• familles des coupes


• algorithme incremental de decomposition en split


• split


• coupe

Informations

• Publié par: pefav
• Nombre de lectures: 67
• Langue: Français

Extrait

Algorithmes Combinatoires (2) D´ecompositionencoupes-famillesbipartitives

Christophe PAUL (CNRS - LIRMM)

November 19, 2009

Familles bipartitives Familles des coupes (splits) ´ ` Theoremederepre´sentation

D´ecompositionencoupes(splits) Graph Labeled Trees (GLT) Graphestotalementd´ecomposables Algorithmeincrementalded´ecompositionensplit ´

Graphes de cercles D´ecompositionencoupedesgraphesdecercle

De´compositionetlargeurderang

lempessditpl to s I beturapiititonno Eex laivirt-nonnoiti

B,

y

|A|>2,|B|>2;

∈

sommets d’un grapheG

= (V,E) est

Coupes (splits)

Une bipartition (A,B) des unecoupe (split)ssi

n1, eKed allceledviai-nrt parttebi I tou ique

ssi

I

∈

x

et

N(B)

∈

y

∈A

et

pour

x

∈

xy

I

E

N(A).

Coupes (splits)

Une bipartition (A,B) des sommets d’un grapheG= (V,E) est unecoupe (split)ssi I |A|>2,|B|>2; I pourx∈Aety∈B,xy∈Essix∈N(B) ety∈N(A).

Exemples de splits I toute bipartition non-triviale de la clique I toute bipartition non-triviale deK

1,n

tiaronti trau ip e b.ell

(A 1 ∩B 1 ,A 2 ∪B 2 )est un split;

Th´ ` eoreme La famille des splits d’un graphe est unefamille bipartitive: si (A 1 ,A 2 ) et (B 1 ,B 1 ) sont deux splits tels queA 1 etB 1 se chevauchent, alors

Familles bipartitive

aledimaf esiellen)estfortehuaucenceehavcuebUn t.lispunst)e 2 A, 1 A(noititrapi splitdes ) son 1 ∪B 1 M 12 B 1 BA,A(M 1 st I ;

I

1 ∩(A I B 2 ),,A 1 ∪B 2 ,A(A 2 ∩∪ 11 B 2 BA,∩ 21 B,)A(