Algorithmes Combinatoires Decomposition modulaire

pages

English

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

English

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

English

Algorithmes Combinatoires (1) Decomposition modulaire Christophe PAUL (CNRS - LIRMM) November 4, 2009

graphes de comparabilite

decomposition en coupes graphes

reconnaissance des graphes de cercles

definitions theoreme de decomposition modulaire

??xy ?

classe de forc¸age de ??xy

algorithme de erhenfeucht

decomposition modulaire

Voir

Publié par

pefav

Nombre de lectures

Langue

English

Algorithmes Combinatoires (1)
Decomposition modulaire
Christophe PAUL
(CNRS - LIRMM)
November 4, 2009Orientation transitive
Decomposition modulaire et familles partitives
De nitions
Theoreme de decomposition modulaire
Graphes totalement decomposables
Intervalles communs et familles faiblement partitives
Algorithmes de decomposition modulaire
Algorithme de Erhenfeucht et al.
Algo de reconnaissance des cographes
Familles bipartitives
Decomposition en coupes
Graphes totalement decomposables
Reconnaissance des graphes de cercles! ! !xy and yz ) xz
Relation de focr age [Gallai] sur l’orientation des ar^etes de E :

soit x = u et yv2= E! !xy uv ssi (1)
soit y = v et xu2= E
Si est la fermeture transitive et re exive de , alors
! !I (xy) est la classe de focager de xy
Graphes de Comparabilite
Un graphe (non-oriente) G = (V;E ) est de comparabilite s’il existe
une orientation transitive de son ensemble d’ar^etes.Relation de focr age [Gallai] sur l’orientation des ar^etes de E :

soit x = u et yv2= E! !xy uv ssi (1)
soit y = v et xu2= E
Si est la fermeture transitive et re exive de , alors
! !I (xy) est la classe de focager de xy
Graphes de Comparabilite
Un graphe (non-oriente) G = (V;E ) est de comparabilite s’il existe
une orientation transitive de son ensemble d’ar^etes.
???
! ! !xy and yz ) xz! ! !xy and yz ) xz
Si est la fermeture transitive et re exive de , alors
! !I (xy) est la classe de focager de xy
Graphes de Comparabilite
Un graphe (non-oriente) G = (V;E ) est de comparabilite s’il existe
une orientation transitive de son ensemble d’ar^etes.
???
Relation de focr age [Gallai] sur l’orientation des ar^etes de E :

soit x = u et yv2= E! !xy uv ssi (1)
soit y = v et xu2= E! ! !xy and yz ) xz
Graphes de Comparabilite
Un graphe (non-oriente) G = (V;E ) est de comparabilite s’il existe
une orientation transitive de son ensemble d’ar^etes.
???
Relation de focr age [Gallai] sur l’orientation des ar^etes de E :

soit x = u et yv2= E! !xy uv ssi (1)
soit y = v et xu2= E
Si est la fermeture transitive et re exive de , alors
! !I (xy) est la classe de focager de xy! ! ! ! ! S( (xy)) =fv2 Vj9 uv2 (xy) ou vu2 (xy)g
Graphes de Comparabilite
Theoreme [Gallai]
Un graphe G = (V;E ) est un graphe de comparabilite ssi pour
! ! toute ar^ete xy2 E , (xy)\ (yx) =;.
???Graphes de Comparabilite
Theoreme [Gallai]
Un graphe G = (V;E ) est un graphe de comparabilite ssi pour
! ! toute ar^ete xy2 E , (xy)\ (yx) =;.
???
! ! ! ! ! S( (xy)) =fv2 Vj9 uv2 (xy) ou vu2 (xy)gGraphes de Comparabilite
Theoreme [Gallai]
Un graphe G = (V;E ) est un graphe de comparabilite ssi pour
! ! toute ar^ete xy2 E , (xy)\ (yx) =;.
???
! ! ! ! ! S( (xy)) =fv2 Vj9 uv2 (xy) ou vu2 (xy)g
Theoreme [Gallai]
!Le support S( (xy)) toute classe de focager
d’un graphe G est un module de G .Graphes de Comparabilite
Theoreme [Gallai]
Un graphe G = (V;E ) est un graphe de comparabilite ssi pour
! !toute ar^ete xy2 E , (xy)\ (yx) =;.
???
! ! ! ! ! S( (xy)) =fv2 Vj9 uv2 (xy) ou vu2 (xy)g
Theoreme [Gallai]
Un graphe G = (V;E ) est un graphe de comparabilite ssi pour
tout module M, le sous-graphe induit G [M] est un graphe de
comparabilite.