b) Quel est le plus petit entier r 1 tel que s
r soit l’application identité ?
c) Calculer explicitement la bijection s
100 (faire la division euclidienne de 100 par r).
11
@ . Calculs dans le groupe des permutations de six objets
a) Combien y a-t-il de permutations d’un ensemble à six éléments ?
b) Pour une permutation de l’ensemble E = {1, 2, 3, 4, 5, 6}, quelles sont les possibilités de décomposition en cycles à supports disjoints ? En déduire que si s est
une permutation de l’ensemble E , alors s
12 est égale à l’identité ou à s
2 .
12.
α β ε γ μ
β 5,6 0
ε 6,1 2,4 0
γ 5,9 2,7 2 0
μ 7,5 7,6 7,7 7,6 0
ζ
4 6,4 6 6 8
Une utilisation des graphes en Biologie. L’étude de l’évolution moléculaire conduit à
définir des écarts entre certaines séquences d’ADN. Les distances entre ces séquences
permettent de faire des hypothèses sur l’ordre dans lequel s’effectuent les duplications de gènes. Voici une
table des distances entre six séquences impliquées dans
la synthèse de protéines fixatrices d’oxygène.
a) Trouver un arbre de longueur minimum reliant ces
séquences.
b) Calculer la longueur d’un plus court chemin entre
deux séquences données.
13. Soit G un graphe orienté connexe ayant une source, un terminal et une capacité
pour chaque arc. On suppose qu’il existe un cycle C = (u 0 , u 1 , . . . , u p−1 , u 0 ) que l’on
peut parcourir en respectant l’orientation des arcs.
a) Montrer que les sommets s et t ne sont pas dans le cycle C .
b) Soit f un flot sur G et soit k un nombre inférieur aux valeurs c(α) − f (α), où
α sont les arcs du cycle C . Pour chaque arc α de G, posons f
(α) = f (α) si α
n’est pas un arc de C et f
(α) = f (α) + k sinon. Montrer que f
est un flot sur
G et que l’on a val(f
) = val(f ).
14.
s
b
t
a
(m)
(m)
(m)
(m)
(1)
Considérons le graphe orienté ci-contre, où la capacité de
chaque arc est indiquée entre parenthèses. Le nombre m est
un entier, s est la source et t est le terminal.
a) On part du flot nul et l’on pratique l’algorithme du flot
maximum en utilisant, lors du marquage, alternativement
les chemins γ 1 = (s, a, b, t) et γ 2 = (s, b, a, t). De combien
augmente la valeur du flot à chaque étape ?
b) Montrer qu’il faut 2m augmentations du flot pour obtenir un flot maximum.
15
@ . Recherche d'un flot maximum. Pour le graphe orienté ci-dessous, les chiffres entre parenthèses indiquent la capacité des arcs. Trouver le flot maximum pouvant transiter
98 – EXERCICES
r soit l’application identité ?
c) Calculer explicitement la bijection s
100 (faire la division euclidienne de 100 par r).
11
@ . Calculs dans le groupe des permutations de six objets
a) Combien y a-t-il de permutations d’un ensemble à six éléments ?
b) Pour une permutation de l’ensemble E = {1, 2, 3, 4, 5, 6}, quelles sont les possibilités de décomposition en cycles à supports disjoints ? En déduire que si s est
une permutation de l’ensemble E , alors s
12 est égale à l’identité ou à s
2 .
12.
α β ε γ μ
β 5,6 0
ε 6,1 2,4 0
γ 5,9 2,7 2 0
μ 7,5 7,6 7,7 7,6 0
ζ
4 6,4 6 6 8
Une utilisation des graphes en Biologie. L’étude de l’évolution moléculaire conduit à
définir des écarts entre certaines séquences d’ADN. Les distances entre ces séquences
permettent de faire des hypothèses sur l’ordre dans lequel s’effectuent les duplications de gènes. Voici une
table des distances entre six séquences impliquées dans
la synthèse de protéines fixatrices d’oxygène.
a) Trouver un arbre de longueur minimum reliant ces
séquences.
b) Calculer la longueur d’un plus court chemin entre
deux séquences données.
13. Soit G un graphe orienté connexe ayant une source, un terminal et une capacité
pour chaque arc. On suppose qu’il existe un cycle C = (u 0 , u 1 , . . . , u p−1 , u 0 ) que l’on
peut parcourir en respectant l’orientation des arcs.
a) Montrer que les sommets s et t ne sont pas dans le cycle C .
b) Soit f un flot sur G et soit k un nombre inférieur aux valeurs c(α) − f (α), où
α sont les arcs du cycle C . Pour chaque arc α de G, posons f
(α) = f (α) si α
n’est pas un arc de C et f
(α) = f (α) + k sinon. Montrer que f
est un flot sur
G et que l’on a val(f
) = val(f ).
14.
s
b
t
a
(m)
(m)
(m)
(m)
(1)
Considérons le graphe orienté ci-contre, où la capacité de
chaque arc est indiquée entre parenthèses. Le nombre m est
un entier, s est la source et t est le terminal.
a) On part du flot nul et l’on pratique l’algorithme du flot
maximum en utilisant, lors du marquage, alternativement
les chemins γ 1 = (s, a, b, t) et γ 2 = (s, b, a, t). De combien
augmente la valeur du flot à chaque étape ?
b) Montrer qu’il faut 2m augmentations du flot pour obtenir un flot maximum.
15
@ . Recherche d'un flot maximum. Pour le graphe orienté ci-dessous, les chiffres entre parenthèses indiquent la capacité des arcs. Trouver le flot maximum pouvant transiter
98 – EXERCICES