TITRE : Structuration des graphes dénombrables

Encadrant B Courcelle

Equipe Methodes Formelles ; Thème Langages Graphes et Logiques

 

Plusieurs notions de structuration des graphes finis ont été définies et

étudiées en détail : décompositions arborescentes, décompositions en

bipartis complets d'où est issue la notion de largeur de clique,

organisation arborescente des graphes d'où est issue la notion de

"rank-width" équivalente à la largeur de clique, décomposition modulaire,

"split-decomposition" (définie par Cunnigham).

Certaines de ces notions ont été étendues aux graphes dénombrables.

Le travail consiste à étudier la "split-decomposition" des graphes

dénombrables, orientés ou non, ainsi que ses relations avec la largeur de

clique et la "rank-width". Plus précisément, il s'agit de répondre aux

questions suivantes :

 

1)      Comment peut-on définir la "split-decomposition" des graphes

dénombrables ?

 

2)      Dans quelle mesure le résultat d'unicité de la "split-decomposition"

montré par Cunigham s'étend aux graphes dénombrables ? Quelle est la

structure des graphes premiers ? Et celle des graphes "fortement

décomposables" ("brittle" et "semi-brittle").

 

3)      Peut-on comme dans le cas des graphes finis définir en Logique du

Second-Ordre Monadique la "split-decomposition" canonique ?

 

4)      Comment peut-on construire pour un graphe fini ou dénombrable la

"split-decomposition" à partir d'un terme fini ou infini sur la signature VR

?

 

5)      Peut-on définir une notion de "rank-width" pour les graphes

dénombrables qui soit associée à une structuration arborescente ? Comment

peut-on construire pour un graphe fini ou dénombrable la

"split-decomposition" à partir de cette structuration (en supposant une

définition  de cette structuration arborescente possible pour le cas

dénombrable).

 

6)      Implanter ces constructions dans le logiciel VISIDIA pour les

graphes  finis, et les approximations finies de graphes infinis spécifiés

par des termes infinis, définies limitation du terme à un niveau fixé.

 

Références :

 

B. Courcelle : Clique-width of countable graphs: a compactness property.

Discrete Mathematics 276 (2004) 127-148.

 

B. Courcelle : The monadic second-order logic of graphs XVI : Split

decompositions and circle graphs, March 2005 (Ne concerne que les graphes

finis ; comporte les references aux travaux de Cunnigham).

 

B. Courcelle et Christian Delhommé (Université de La Réunion) : The modular

decomposition of countable graphs : Constructions in Monadic Second-Order

Logic, CSL 2005, Actes LNCS. (Utile pour le point 3)

 

S. Oum et P. Seymour : Approximating clique width and branch-width , A

paraître JCT B, (Comparaison de "rank-width" et "clique-width").

 

Logiciel Visidia :

http://www.labri.fr/Recherche/LLA/visidia/

Voir http://www.labri.fr/Perso/~courcell/ActSci.html pour les articles non

encore parus.

Contact : courcell@labri.fr