Circuits
dans le graphe de de Bruijn
Encadrants:
Fabrice
Philippe et Patrice
Séébold,
LIRMM
Contexte
Les graphes de de Bruijn apparaissent dans divers contextes, par
exemple en matière de réseaux ou encore
d'automates. Leur combinatoire connue est très riche. Nous
nous intéressons ici à plusieurs
problèmes énumératifs liés
à des circuits particuliers de ces graphes.
Le graphe de de Bruijn d'ordre k
pour un alphabet A
= {a1,...,
an}
de taille n
est défini de la façon suivante:
- Il a pour sommets l'ensemble des mots de longueur k
sur A.
- Chaque sommet a n arcs sortants
étiquetés par les lettres de A.
- Les suivants d'un sommet s'obtiennent en supprimant sa
première lettre et en ajoutant une des n
lettres possibles
à la fin.
Exemple,
pour n
= 2 et k =
3:
On se promène dans le graphe ci-dessus, sans passer deux
fois
par le même arc, en utilisant l'algorithme
suivant:
- Choisir un sommet de départ.
- Au sommet en cours, sortir en premier par
l'arc marqué a,
et par b seulement
si on est déjà sorti par a.
- S'arrêter lorsqu'on ne peut plus continuer
(on est déjà sorti par a
et par b).
On parcourt ainsi un circuit (pourquoi?), et un circuit eulérien
si, et seulement si,
on est parti de bbb
(ceci est un cas particulier d'un
résultat dû
à de Bruijn lui-même). Si l'on essaie tous les
sommets de
départ, on parcourt les chemins suivants:
aaa abaaa
aab aaaabbaab
aba aaababa
abb aaaabaabbbababb
baa aabaabbaa
bab aaaababbaabbbab
bba aaabaabbababbba
bbb aaaabaabbababbbb
Objectifs
Déterminer, pour n
= 2 et k fixé, les différentes longueurs
possibles des circuits
parcourus selon l'algorithme fourni.
Déterminer le nombre de sommets de départ
fournissant un circuit de longueur donnée.
On pourra ensuite regarder ce qui se passe pour n
≥ 3.