Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

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
lempessditpltosIbeturapiititonnoEexlaivirt-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,eKedallceledviai-nrtparttebiItouique
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; IpourxAetyB,xyEssixN(B) etyN(A).
Exemples de splits Itoute bipartition non-triviale de la clique Itoute bipartition non-triviale deK
1,n
tiarontitrauipeb.ell
(A1B1,A2B2)est un split;
Th´ ` eoreme La famille des splits d’un graphe est unefamille bipartitive: si (A1,A2) et (B1,B1) sont deux splits tels queA1etB1se chevauchent, alors
Familles bipartitive
aledimafesiellen)estfortehuaucenceehavcuebUnt.lispunst)e2A,1A(noititrapisplitdes)son1B1M12B1BA,A(M1stI;
I
1(AIB2),,A1B2,A(A211B2BA,21B,)A(
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