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