X/ENS Informatique A MP 2021

Thème de l'épreuve Facteurs dans les mots binaires
Principaux outils utilisés programmation OCaml, fonctions récursives, arbres, chaînes de caractères, programmation dynamique, graphes, complexité
Mots clefs de Bruijn, suffixe, facteur, bio-informatique, peigne, arbre binaire, mots, accumulateur, graphe eulérien

Corrigé

 : 👈 gratuite pour tous les corrigés si tu crées un compte
👈 l'accès aux indications de tous les corrigés ne coûte que 1 € ⬅ clique ici
👈 gratuite pour tous les corrigés si tu crées un compte
- - - - - - - - - - - - - - - - - - - - - - - - -

Énoncé complet

(télécharger le PDF)
                                

Rapport du jury

(télécharger le PDF)
              

Énoncé obtenu par reconnaissance optique des caractères


ECOLE POLYTECHNIQUE
ECOLES NORMALES SUPERIEURES
CONCOURS D'ADMISSION 2021

MARDI 13 AVRIL 2021
14h00 - 18h00
FILIERE MP

-

Epreuve n° 4

INFORMATIQUE A (XULCR)

Durée : 4 heures
L'utilisation des calculatrices n'est pas autorisée pour
cette épreuve

Cette composition ne concerne qu'une partie des candidats de la
filière MP, les autres candidats effectuant simultanément la
composition de Physique et Sciences de l'Ingénieur.
Pour la filière MP, il y a donc deux enveloppes de Sujets pour
cette séance.

Facteurs dans les mots binaires
Ce sujet traite de mots sur un alphabet

{0, 1}. On s'intéresse à leurs facteurs, notamment aux

facteurs répétés dans un mot et aux mots ayant le maximum de facteurs distincts. L'algorithmique
des facteurs est particulièrement utile dans le domaine de la bio-informatique, où l'analyse de
mots très longs, à savoir les génomes, requiert des structures de données ecaces.

Mots.

mot m est une suite nie m0 m1 . . . m`-1 de lettres de l'alphabet {0, 1}. Sa longueur `
`(m) et sa lettre d'indice i est notée mi pour 0  i  `(m)-1. Le mot vide, de longueur 0,
. On note c` le mot de longueur ` formé de ` caractères c.
Un

est notée
est noté

m = m0 m1 . . . m`(m)-1
0 =
leur concaténation comme le mot mm
0
0
gueur `(mm ) = `(m) + `(m ).
Pour

Pour

deux

mots

0  i  j  `(m),

on note

m[i..j[

m0 = m00 m01 . . . m0`(m0 )-1 , on dénit
m0 m1 . . . m`(m)-1 m00 m01 . . . m0`(m0 )-1 de lon-

et

le mot

mi mi+1 . . . mj-1 ,

facteur de m.
0  i = j  `(m).
m[i..`(m)[) et on le

qui est appelé

On note que le mot vide est un facteur de n'importe quel mot, obtenu pour
Un

préxe

(resp.

suxe )

m[..j[

(resp.

m[i..[).

note

de

m

est un facteur de la forme

· F(m) = {m[i..j[ | 0  i  j  `(m)}
· P(m) = {m[..j[ | 0  j  `(m)}
· S(m) = {m[i..[ | 0  i  `(m)}

Arbres binaires.

Un

m[0..j[

(resp.

On note

soit comme l'arbre vide, noté

·

soit comme un

l'ensemble des préxes de

l'ensemble des suxes de

arbre binaire

·

l'ensemble des facteurs de

m;

m;

m.

est déni récursivement de la manière suivante :

V,

qui ne contient aucun n÷ud ;

n÷ud, noté N (x, g, d) et appelé racine, où x est l'information stockée dans
sous-arbre gauche et d est un arbre binaire appelé
sous-arbre droit.
le n÷ud,

On note

g

n(a)

est un arbre binaire appelé

le nombre de n÷uds et

n(V ) = h(V ) = 0,

Langage OCaml.
partir de la liste vide
est l'élément

x

h(a)

la hauteur d'un arbre binaire

n(N (x, g, d)) = 1 + n(g) + n(d)

et

a,

dénis par

h(N (x, g, d)) = 1 + max(h(g), h(d)).

Ce sujet utilise les listes et les tableaux d'OCaml. Une liste est construite à

[]

et de la construction

et dont la queue est la liste

formée des éléments de la liste

l

l.

x :: l

qui renvoie une nouvelle liste dont la tête

L'appel de

en ordre inverse.

1

List.rev l

renvoie une nouvelle liste,

On peut créer des tableaux avec les deux fonctions
de

Array.make n x crée un tableau
Array.of_list l crée un

L'appel de

de taille

n

Array.make

et

Array.of_list.

L'appel

dont toutes les cases contiennent la valeur

tableau contenant, dans l'ordre, les éléments d'une liste

x.
l.

Array.length renvoie la taille
d'un tableau. Pour un tableau tab, on accède à l'élément d'indice i avec tab.(i) et on le modie
avec tab.(i) <- v. Les cases d'un tableau sont numérotées à partir de 0. La fonction Dans tout le sujet, on représente un mot par un tableau d'entiers, ne contenant que des entiers 0 ou 1. On se donne donc le type suivant : type mot = int array (* ne contient que des 0/1 *) Dans les fonctions demandées, on ne cherchera jamais à vérier que les tableaux passés en arguments ne contiennent que des 0 et des 1. Complexité. Par complexité (en temps) d'un algorithme A on entend le nombre d'opérations élémentaires (comparaison, addition, soustraction, multiplication, division, aectation, test, etc.) A dans le cas le pire. Lorsque la complexité dépend d'un ou plu0 , · · · , r-1 , on dit que A a une complexité en O(f (0 , · · · , r-1 )) s'il existe C > 0 telle que, pour toutes les valeurs de 0 , · · · , r-1 susamment grandes

nécessaires à l'exécution de
sieurs paramètres
une constante

(c'est-à-dire plus grandes qu'un certain seuil), pour toute instance du problème de paramètres

0 , · · · , r-1 ,

la complexité est au plus

Dépendances.

C · f (0 , · · · , r-1 ).

Ce sujet est conçu pour être traité linéairement. La partie I est nécessaire

pour la partie II, et ces deux premières parties motivent la partie III, elle-même utilisée dans
la question 22 de la partie IV. En revanche, les questions 20 et 21 de la partie IV ainsi que la
partie V sont indépendantes du reste du sujet.

Partie I. Arbres de mots
Dans cette partie, on introduit une structure de données, appelée

arbre de mots, qui représente

un ensemble ni de mots. Un arbre de mots est un arbre binaire dont chaque n÷ud contient un

a représente un ensemble ni de mots, noté M(a), déni comme suit.
a est vide, alors M(a) est l'ensemble vide. Si l'arbre a est de la forme N (b, a0 , a1 ),
M(a) est l'ensemble des mots suivants :

booléen. Un arbre de mots
Si l'arbre
alors

true ;

·

le mot vide

·

les mots de la forme

0m

pour

m  M(a0 ) ;

·

les mots de la forme

1m

pour

m  M(a1 ).

si le booléen

b

est

Autrement dit,

M(a) est l'ensemble des mots correspondant aux chemins menant de la racine à
un n÷ud contenant true, en utilisant le caractère 0 quand on va à gauche et le caractère 1 quand
2

on va à droite. Ainsi, l'arbre

a1

T

Dans tous les dessins, on utilise

T

(resp.

F)

pour le booléen

F

T

F

F

F
T

T

a1

(resp.

F

F

T

T

T

true

F

F

F

M(a1 ) = {, 10, 11}.
false).

de la gure 1 représente l'ensemble de mots

F

F
T

F
F

T

T

a2

F
F
T

T
T

a3

T

a4

Figure 1  Des arbres de mots.
On note qu'un ensemble de mots peut être représenté par une innité d'arbres de mots. En
eet, il sut de remplacer un arbre vide par un n÷ud

N (false, V, V )

pour obtenir un autre

arbre de mots représentant le même ensemble de mots. Par exemple, l'arbre vide
un n÷ud

réduit

est

N (false, V, V )

V

et l'arbre à

représentent tous les deux l'ensemble vide. On dit qu'un arbre de mots

dès lors que tout n÷ud dont les deux sous-arbres sont vides contient le booléen

true.

Dans toute la suite, on ne manipulera que des arbres de mots réduits.

Question 1.
Question 2.

a2 de la gure
{, 00, 010, 1, 110, 111}.

Donner l'ensemble de mots représenté par l'arbre

arbre de mots réduit représentant l'ensemble de mots

1. Dessiner un

Montrer que, pour tout ensemble ni de mots, il existe un unique arbre de mots

réduit qui le représente.

Dans la suite, on note

M(A(M )) = M
de mots réduit

A(M )

l'arbre de mots réduit de l'ensemble ni de mots

pour tout ensemble ni de mots

M

et inversement

M.

On a donc

A(M(a)) = a pour tout arbre

a.

Pour représenter un arbre de mots en OCaml, on se donne le type suivant

type am =
| V
| N of bool * am * am
où

V

représente l'arbre vide et

N

représente un n÷ud. Par exemple, l'arbre

a1

de la gure 1 est

représenté par la valeur suivante :

N (true, V, N (false, N (true, V, V), N (true, V, V)))

Question 3.

Écrire une fonction zeros_puis_uns: int -> am qui reçoit en argument un enn  0 et qui renvoie l'arbre de mots réduit représentant tous les mots de la forme 0p 1q avec
p + q = n. L'arbre a3 de la gure 1 donne un exemple d'un tel arbre pour n = 3.
tier

Question 4.
entiers

k  0

Écrire une fonction
et

n  0

k_uns: int -> int -> am

qui reçoit en arguments deux

et qui renvoie l'arbre de mots réduit représentant tous les mots de

3

longueur au plus

n

et contenant exactement

exemple d'un tel arbre pour

k=2

et

k

caractères 1. L'arbre

a4

de la gure 1 donne un

n = 3.

Indication : Pour s'assurer que l'arbre renvoyé est bien réduit, on pourra se servir de la fonction
suivante.
let sN = function
| (false, V, V) -> V
| (b, a0, a1) -> N (b, a0, a1)

Question 5.

Écrire une fonction

a et renvoie le
n(a), mais il n'est

compter: am -> int qui reçoit en argument
M(a). La complexité en temps doit

mots

cardinal de l'ensemble

en

pas demandé de la justier.

Question 6.

chercher: am -> mot -> bool qui reçoit
détermine si m appartient à l'ensemble M(a).

Écrire une fonction

arbre de mots

a

et un mot

temps doit être linéaire en

Question 7.

m et
`(m),

un arbre de
être linéaire

en arguments un
La complexité en

mais il n'est pas demandé de la justier.

enumerer: am -> mot list qui reçoit en argument un arbre
M(a) sous la forme d'une liste. La complexité en
P
taille du résultat
mM(a) `(m). On justiera la complexité.

Écrire une fonction

de mots réduit

a

et renvoie l'ensemble de mots

temps doit être linéaire en la

Indication : On pourra écrire une fonction récursive auxiliaire qui reçoit en arguments
· une liste acc dans laquelle on accumule les mots déjà construits,
· une liste pref contenant les lettres rencontrées le long du chemin menant du n÷ud courant

à la racine,

· le sous-arbre t dont la racine est le n÷ud courant,

et qui renvoie la liste acc complétée avec tous les mots de M(t) auxquels on a ajouté le préxe
donné par la liste pref.

Question 8.

Écrire une fonction

de mots réduit

M(a)  {m}.

a

et un mot

m

ajouter: am -> mot -> am qui reçoit en arguments un arbre

et renvoie l'arbre de mots réduit représentant l'ensemble de mots

La complexité en temps doit être linéaire en

`(m),

mais il n'est pas demandé de la

justier.

A(M ) correspondent à l'ensemble
{m[..i[ | m  M et 0  i  `(m)}. En eet, les mots donnés par les chemins de la racine
aux n÷uds de A(M ) (en utilisant 0 quand on va à gauche et 1 quand on va à droite) sont
précisément les préxes d'au moins un mot de M .
Pour la suite, on remarque que les n÷uds de l'arbre de mots

de mots

Partie II. Arbre des suxes
m et on dénit l'arbre des suxes de m, noté AS(m),
suxes de m, c'est-à-dire AS(m) = A(S(m)).

Dans cette partie, on considère un mot
comme l'arbre de mots réduit de tous les

4

Question 9.

Donner l'arbre

Question 10.

am -> mot

pour le mot

AS(m)

AS(m) ? En déduire une fonction retrouver_mot:
de l'arbre AS(m) de ses suxes. La complexité en

Quelle est la hauteur de l'arbre

m à partir
n(AS(m)), mais il

qui retrouve le mot

temps doit être linéaire en

Question 11.

m = 1011.

n'est pas demandé de la justier.

AS(m) correspondent aux facteurs distincts
AS(m) est au moins linéaire et au plus
quadratique en `(m). Montrer que ces bornes sont atteintes, c'est-à-dire que pour tout entier `,
2
il existe un mot m de longueur ` tel que l'arbre AS(m) a ` + 1 n÷uds (resp. au moins C` n÷uds
où C est une constante indépendante de ` que l'on explicitera).
de

m.

Montrer que les n÷uds de l'arbre

En déduire que le nombre de n÷uds de l'arbre

Des bornes plus précises sur le nombre de facteurs distincts de

m

seront étudiées dans la

partie IV.

Partie III. Arbre des facteurs
Dans cette partie, on introduit une structure de données potentiellement plus compacte pour
représenter l'arbre des suxes d'un mot

m

xé, appelée

arbre des facteurs.

Cette structure est

basée sur les deux idées suivantes :

·

dans l'arbre de suxes

AS(m),

false

un chemin formé de n÷uds dont le booléen est

et

dont l'un des sous-arbres est vide peut être compacté dans le n÷ud suivant, quitte à se
rappeler de la séquence de caractères correspondante (0 quand on va à gauche et

1

quand

on va à droite) ;

·

une telle séquence de caractères se représente de façon compacte par une paire d'entiers

(p, q)

qui désigne le facteur

m[p..q[.

On considère donc un arbre binaire dont chaque n÷ud contient deux entiers

0  p  q  `(m)

a
M(a)

et un booléen. Un tel arbre

a est vide, alors
N (p, q, b, a0 , a1 ), alors M(a) est l'ensemble

ni comme suit. Si l'arbre
forme

les mots de la forme

m[p..q[0f

pour

f  M(a0 ) ;

·

les mots de la forme

m[p..q[1f

pour

f  M(a1 ).

L'arbre

a

est

est un arbre des facteurs du mot

de tous les suxes de

m.

m

si l'ensemble

On dit qu'un arbre des facteurs est

au moins un des sous-arbres est vide contient le booléen

dé-

est de la

M(a)

réduit

true.

est exactement l'ensemble

dès lors que tout n÷ud dont

Ainsi, l'arbre de la gure 2 est

10110100. Dans tous les dessins, on représente l'information
N (p, q, b, a0 , a1 ) par p..q(T) si b est true et p..q(F) si b est false.

un arbre des facteurs réduit du mot
contenue dans un n÷ud

que

true ;

·

b

a

q tels
M(a)

des mots suivants :

le mot

si le booléen

et

est l'ensemble vide. Si l'arbre

·

m[p..q[

p

représente l'ensemble des mots

5

8..8(T)
8..8(T)
8..8(T)

6..6(F)
6..6(F)

7..8(T)

7..7(F)

4..8(T)

8..8(T)

4..8(T)
6..6(F)

7..8(T)

4..8(T)

Figure 2  Un arbre des facteurs réduit du mot 10110100.
Attention : Un arbre des facteurs du mot m n'est pas un arbre de mots de tous les facteurs de m,
mais une représentation compacte de l'arbre des suxes de m. On parle d' arbre des facteurs car
il permet de manipuler facilement tous les facteurs de m, comme on le verra plus loin.

Question 12.

Pour chaque arbre

a

de la gure 3, donner l'ensemble

m = 01001,

d'un arbre des facteurs pour le mot

5..5(T)
5..5(T)

2..5(T)

et indiquer s'il s'agit

5..5(T)

4..4(F)
4..5(T)

M(a)

et s'il est réduit.

3..5(T)

4..4(F)
4..5(T)

5..5(T)
5..5(T)

5..5(T)

4..4(F)

3..5(T)

4..5(T)

3..5(T)

a5

5..5(T)

5..5(T)
3..5(T)

a6

3..5(F)
4..5(T)

a7

Figure 3  Des arbres.
On peut se convaincre facilement qu'il existe toujours au moins un arbre des facteurs pour

m.

tout mot

En eet, il sut de construire l'arbre des suxes

d'ajouter dans chaque n÷ud la paire d'entiers

(0, 0).

AS(m)

de

m

de la partie II et

Pour obtenir un arbre des facteurs réduit,

il sut alors de réduire cet arbre comme expliqué au début de cette partie, en compactant tous
les n÷uds dont le booléen est

false

et dont un des sous-arbres est vide. On verra plus loin une

procédure pour construire directement un arbre des facteurs réduit.

On montre maintenant qu'un arbre des facteurs réduit du mot

m est compact en comparaison

de l'arbre des suxes de la partie II qui pouvait être quadratique comme observé à la question 11.

Question 13.
n÷uds si
le mot

m

est

Soit

0`

a

ou

un arbre des facteurs réduit d'un mot

1`

pour

`  0.

m.

On note que l'arbre

En supposant que les deux lettres

0

et

1

a

a

`+1

apparaissent dans

m,

1. montrer que le nombre de n÷uds de

a

ayant au moins un sous-arbre vide est au plus

a en fonction de `(m), et montrer
` > 0, il existe un mot de longueur `

2. en déduire une borne supérieure du nombre de n÷uds de
que cette borne est atteinte (c'est-à-dire que pour tout

dont un arbre des facteurs a précisément ce nombre de n÷uds).

6

`(m),

Pour représenter un arbre des facteurs en OCaml, on se donne le type

type af =
| V
| N of int * int * bool * af * af
où

V

représente l'arbre vide et

N

représente un n÷ud. On rappelle que le mot

cette partie. On pourra supposer qu'il est dans une variable globale

m

est xé dans

m.

Question 14.

Écrire une fonction nb_facteurs: af -> int qui reçoit en argument un arbre
a du mot m et renvoie le nombre de facteurs distincts de m. La complexité en temps
linéaire en n(a), mais il n'est pas demandé de la justier.

des facteurs
doit être

Question 15. Écrire une fonction plpc: mot -> int -> int -> mot -> int -> int -> int
plus long préxe commun) qui prend en arguments un mot m1 avec deux in0  p  q  `(m1 ) et un mot m2 avec deux indices 0  i  j  `(m2 ), et qui renvoie
plus grand k tel que p + k  q et i + k  j et m1 [p..p + k[ = m2 [i..i + k[. La complexité en

(pour
dices
le

temps doit être linéaire en le résultat, mais il n'est pas demandé de la justier.

Question 16.

facteur: af -> mot -> bool qui reçoit en arguments un
arbre des facteurs a du mot m et un mot f et détermine si f est un facteur de m. La complexité
en temps doit être linéaire en `(f ). On justiera la complexité.

Question 17.

Écrire une fonction

facteurs: af -> mot list qui reçoit en argument un arbre
a du mot m et renvoie l'ensemble des facteurs F(m) sous la forme d'une liste.

Écrire une fonction

des facteurs réduit

Chaque facteur doit apparaître une fois et une seule dans cette liste. La complexité en temps
doit être linéaire en la taille du résultat

P

f F(m) `(f ). On justiera la complexité.

On montre maintenant comment construire un arbre des facteurs réduit pour le mot

m. Pour

m,

dans un

cela, on part de l'arbre vide et on ajoute successivement tous les suxes du mot
ordre arbitraire. Un suxe

m[i..[

est ajouté à l'arbre courant

a

de la manière suivante :

N (i, `(m), true, V, V ),

·

si

a=V,

·

si

a = N (p, q, b, a0 , a1 ), on cherche le plus grand k tel que p + k  q
m[p..p + k[ = m[i..i + k[. On distingue alors deux cas :

on construit l'arbre

et

i + k  `(m)

et tel

que

si

p+k  af -> af ci0  i  `(m) et un arbre a en cours de construction
suxe m[i..[ à l'arbre a en suivant la procédure décrite

Compléter le code de la fonction

dessous, qui reçoit en arguments une position
et renvoie l'arbre obtenu en ajoutant le
ci-dessus.

let rec ajouter_suffixe i a =
let n = Array.length m in
match a with
| V -> N (i, n, true, V, V)
| N (p, q, b, a0, a1) ->
let k = plpc m p q m i n in
if p + k < q then (* CAS 1 *) ... else (* CAS 2 *) ... 8 On donnera uniquement dans la copie le code correspondant à fonction plpc (* CAS 1 *) et (* CAS 2 *). La est celle décrite à la question 15. Partie IV. Application : plus long facteur répété facteurs répétés du mot m, c'est-à-dire aux tri(i, j, k) avec 0  i  i + k  `(m) et 0  j  j + k  `(m) tels que i 6= j et m[i..i + k[ = m[j..j + k[. On cherche la longueur maximale d'un facteur répété dans m. On Dans cette partie, on s'intéresse aux plets commence par un algorithme naïf. Question 20. dans m. plfr1: mot -> int

Écrire une fonction

reçoit en argument un mot

m

(pour plus long facteur répété) qui

non vide et renvoie la longueur d'un plus long facteur répété

La complexité en temps doit être

O(`(m)3 ),

mais il n'est pas demandé de la justier.

Pour améliorer la complexité de ce calcul, on utilise maintenant un algorithme de program-

0  i, j  `(m), on note c(i, j) la longueur du plus long suxe commun
m[0..i[ et m[0..j[. On rappelle qu'en OCaml, une matrice est un tableau de tableaux. L'appel
de Array.make_matrix p q x crée une matrice de taille p × q dont toutes les cases contiennent
la valeur x. Pour une matrice mat, on accède à l'élément (i, j) avec mat.(i).(j) et on le modie
avec mat.(i).(j) <- v. mation dynamique. Pour de Question 21. Écrire une fonction plfr2: mot -> int

La complexité en temps doit être

O(`(m)2 ),

m non
m en construisant la table des c(i, j).

qui reçoit en argument un mot

vide et renvoie la longueur d'un plus long facteur répété dans

mais il n'est pas demandé de la justier.

On suppose maintenant qu'on connaît un arbre des facteurs
les plus longs facteurs répétés dans le mot

m

a

du mot

m.

On observe que

correspondent aux n÷uds internes de profondeur

maximale de l'arbre des facteurs. La profondeur est ici considérée comme étant égale à la longueur
du mot représenté par le chemin depuis la racine, c'est-à-dire que chaque n÷ud
contribue

q-p+1

Question 22.
facteurs réduit
dans

m.

Écrire une fonction

a

N (p, q, b, a0 , a1 )

à la profondeur.

d'un mot

m

plfr3: af -> int

qui reçoit en argument un arbre des

non vide et renvoie la longueur d'un plus long facteur répété

La complexité en temps doit être en

O(`(m)).

On justiera la complexité.

Partie V. Mot contenant un maximum de facteurs distincts
Dans cette partie, on cherche des mots ayant un maximum de facteurs distincts. Pour un
mot

m

0  k  `(m), on note fk (m) le nombre de facteurs
P`(m)
f (m) = k=0 fk (m) le nombre de facteurs distincts de m.

et un entier

longueur

k,

et

Question 23.

Montrer que pour tout mot

m

sur l'alphabet

{0, 1}

on a

fk (m)  min(2k , `(m) - k + 1).

9

distincts de

et tout entier

m

de

0  k  `(m),

100

110

000

010

101

001

111
011

Figure 5  Le graphe G4 .
On considère maintenant un entier
mot de longueur
exemple, le mot

k

xé. On suppose qu'il existe un mot

m

tel que chaque

k sur l'alphabet {0, 1} apparaisse exactement une fois comme facteur de m. Par
0001011100 a cette propriété pour k = 3. On montrera plus tard qu'il tel mot

existe toujours.

Question 24.

Déterminer la longueur d'un tel mot et que ce mot atteint le nombre maximum

de facteurs distincts parmi les mots de longueur

Il reste donc à montrer qu'il existe un mot
exactement une fois comme facteur de
un graphe orienté particulier, appelé

G est
v à w.

Un graphe orienté
existe un chemin de

Un graphe orienté
au degré sortant de

v.

G

dit

eulérien
cycle eulérien

Question 26.

G

k

si, pour toute paire de sommets

si, pour tout sommet

v,

dans un graphe orienté

apparaisse

le degré entrant de

G

v

et

w,

v

est égal

il

est un cycle passant une et

G.

Montrer que tout graphe eulérien

et que le graphe

tel que chaque mot de longueur

fortement connexe

une seule fois par chaque arête de

Question 25.

m

Pour cela, on va considérer des cycles eulériens dans

graphe de de Bruijn.

est dit

Un

m.

`(m).

privé des arêtes du cycle

C

G ayant au moins une arête admet un cycle C ,

est encore eulérien.

En déduire qu'un graphe orienté fortement connexe est eulérien si et seulement

s'il contient un cycle eulérien.

Finalement, on considère le graphe orienté

·

les sommets sont tous les mots à

·

les arêtes sont les couples
sur l'alphabet

mot

m

dont

lettres sur l'alphabet

{0, 1},

(m1 . . . mk-1 , m2 . . . mk ) pour tous les mots m1 . . . mk

à

k

lettres

{0, 1}.

Par exemple, le graphe orienté

Question 27.

k-1

Gk

G4

est représenté à la gure 5.

Montrer que le graphe

tel que chaque mot de longueur

Gk admet un cycle eulérien.
k apparaisse exactement une

10

En déduire qu'il existe un
fois comme facteur de

m.