Algorithmes Combinatoires (1) Décomposition modulaire

Algorithmes Combinatoires (1)
Decomposition modulaire
Christophe PAUL
(CNRS - LIRMM)
November 4, 2009Orientation 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 ) ...