Algorithmes Combinatoires Decomposition en coupes familles bipartitives

pages

Français

Documents

Écrit par
Christophe Paul

Publié par
pefav

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

Français

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

pefav

Nombre de lectures

Langue

Français

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

Voir

Publié par

pefav

Nombre de lectures

Langue

Français

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

|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

∈

N(B)

∈

∈A

pour

∈

N(A).

Coupes (splits)

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

Exemples de splits Itoute bipartition non-triviale de la clique Itoute bipartition non-triviale deK

1,n

tiarontitrauipeb.ell

(A1∩B1,A2∪B2)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)son1∪B1M12B1BA,A(M1stI;

1∩(AIB2),,A1∪B2,A(A2∩∪11B2BA,∩21B,)A(

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

Livre audio en ligne - Développement personnel Livre en ligne Tout le catalogue Tous les Intérêts

Algorithmes Combinatoires Decomposition en coupes familles bipartitives

YouScribe

Le catalogue

Le service

Les conditions