Algorithmes Combinatoires (1) Décomposition modulaire

pages

Français

Documents

Écrit par
Christophe Paul (Cnrs - Lirmm)

Publié par
Nosher

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

pages

Français

Documents

Lire

Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres

Publié par

Nosher

Nombre de lectures

206

Langue

Français

Voir

Publié par

Nosher

Nombre de lectures

206

Langue

Français

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.

Voir