ENS Informatique MP PC 2008Sujet

Filière MP (groupe I)

INFORMATIQUE

Préliminaires

Définitions et notations

Partie 1. Arbres couvrants et cycles fondamentaux

Question 1.1.

1. (a) Montrer que le nombre de cycles élémentaires de G est fini.
   (b) Montrer que G admet au moins un arbre couvrant.
2. Montrer que tout arbre couvrant de G a exactement n − 1 arêtes.
3. Écrire un pseudo-programme SansCycleElem qui, étant donné G, détermine si G ne contient aucun cycle élémentaire. Pourquoi est-il correct et quel est son coût ?

Question 1.2.

1. Donner la structure d'adjacence d'un arbre couvrant de G = (S, A) pour S = {1, 2, 3, 4, 5} et A = {(1, 2), (1, 3), (1, 4), (2, 3), (3, 4), (3, 5), (4, 5)}.
2. Écrire un pseudo-programme ArbreCouvrant qui, étant donné G, calcule la structure d'adjacence d'un arbre couvrant de G. Pourquoi est-il correct et quel est son coût ?

Question 1.3.

1. Vérifier l'existence et l'unicité de la chaîne élémentaire utilisée à la fin de la partie Définitions et notations pour définir le cycle fondamental φ_a.
2. Étant donné T un arbre couvrant de G, on note L_T la somme des longueurs des éléments de φ(G, T).
   (a) Majorer L_T en fonction de n.
   (b) On suppose ici que m = 1/2n(n − 1). En calculant la valeur de L_T pour deux arbres couvrants de G, montrer que l'ordre de grandeur de L_T dépend de T.
3. (a) Écrire un pseudo-programme Phi qui, étant donné G, calcule un ensemble de cycles fondamentaux de G (c'est-à-dire φ(G, T) pour T un arbre couvrant quelconque de G ). Pourquoi est-il correct ?
   (b) Exprimer, en le justifiant, le coût de Phi en fonction de m et de la somme des longueurs des cycles fondamentaux calculés.

Partie 2. Bases minimales de l'espace des cycles

Question 2.1.

1. Soient e ∈ E et f ∈ E.
   (a) Soit α ∈ K. Quel sous-ensemble de A chacune des trois expressions αe, − e, e + f représente-t-elle?
   (b) Caractériser en termes d'arêtes communes le fait que ⟨e, f⟩ = 1.
2. Soit S un support. Montrer qu'il existe C ∈ C(G) tel que ⟨C, S⟩ = 1.
3. Montrer que φ(G, T) est une base de C(G).

pour i de 1 à N faire
    Si \leftarrow un support tel que }\langle\mp@subsup{C}{k}{},\mp@subsup{S}{i}{}\rangle=0,1\leqk\leqi-
    Ci \leftarrow un cycle de G de poids minimal tel que }\langle\mp@subsup{C}{i}{},\mp@subsup{S}{i}{}\rangle=
fin pour

Question 2.2.

1. Pour 2 ≤ i ≤ N, montrer que C_i est linéairement indépendant de C_1, …, C_(i − 1).
2. Montrer que {C_1, …, C_N} est une base minimale de C(G).

Question 2.3.

1. (a) Soit i ∈ {2, …, N} fixé. Écrire un pseudo-programme Support qui, étant donnés les vecteurs d'incidence des cycles C_1, …, C_(i − 1) de G, calcule le vecteur d'incidence d'un support S_i tel que ⟨C_k, S_i⟩ = 0 pour 1 ≤ k ≤ i − 1.
   (b) Donner en le justifiant le coût de Support. Quel coût total (en fonction de m) obtient-on alors pour {S_i}_(1 ≤ i ≤ N) avec cette méthode?
2. (a) Montrer comment calculer {S_i}_(1 ≤ i ≤ N) en introduisant pour 1 ≤ i ≤ N des ensembles de supports {R_j^((i))}_(i ≤ j ≤ N) qui vérifient les deux conditions suivantes :

• pour 1 ≤ i ≤ N, R_i^((i)), …, R_N^((i)) sont linéairement indépendants;
• ⟨C_k, R_j^((i))⟩ = 0 pour 1 ≤ k < i ≤ j ≤ N et 2 ≤ i ≤ N.
  (b) Réécrire l'algorithme BaseMinimale1 de façon à ce que l'itération i calcule S_i, C_i et, si i < N, R_(i + 1)^((i + 1)), …, R_N^((i + 1)). Quel nouveau coût total (en fonction de m ) obtient-on pour {S_i}_(1 ≤ i ≤ N) ?

Question 2.4.

• si (s, t) ∉ S_i alors G_i possède les deux arêtes (s^+, t^+)et (s^−, t^−), chacune de poids w((s, t));
• si (s, t) ∈ S_i alors G_i possède les deux arêtes (s^+, t^−)et (s^−, t^+), chacune de poids w((s, t)).

1. Soit G = (S, A) où S = {1, 2, 3, 4, 5} et A = {(2, 3), (4, 5), (1, 2), (1, 3), (1, 4), (1, 5)}. On suppose de plus que w(a) = 0 pour tout a ∈ A. Dessiner les sommets et les arêtes de G et G_i pour S_i = {(2, 3), (4, 5)}.
2. Pour s ∈ S donné, soit σ = (s_j)_(0 ≤ j ≤ λ) une chaîne reliant s_0 = s^+à s_λ = s^−dans G_i.
   (a) Montrer qu'à σ correspond un cycle de G, qu'on notera C, tel que w(C) ≤ w(σ) et ⟨C, S_i⟩ = 1.
   (b) On suppose que σ est représenté de façon partielle par un tableau chaine d'entiers tel que, pour 1 ≤ j ≤ λ, chaine [j] = k si s_(j − 1) = s^α, s_j = t^β, (s, t) = a_k et α, β ∈ { +, − }. Écrire un pseudo-programme qui calcule le vecteur d'incidence de C à partir de chaine. Quel est son coût ?
   (c) Montrer que si w(σ) = min{δ(t^+, t^−) : t ∈ S} alors w(C) = min{w(D) : D ∈ C(G) et ⟨D, S_i⟩ = 1}.
3. On suppose disposer d'un algorithme PlusCourteChaine de coût O(m + nlogn) qui, à partir de G, de S_i et d'un sommet s de G, calcule le couple (distance, chaine) où distance = δ(s^+, s^−)et où chaine est la représentation partielle (définie à la question 2.4.2.(b)) d'une chaîne σ reliant s^+à s^−dans G_i et telle que w(σ) = δ(s^+, s^−).
   (a) Écrire un pseudo-programme calculant le vecteur d'incidence de C_i à partir de G et S_i. Quel est son coût ?
   (b) Conclure en exprimant le coût de l'algorithme BaseMinimale1 en fonction de m et n.

Question 2.5.

1. (a) Soient P ∈ K^(p × q) et Q ∈ K^(q × p) avec 1 ≤ p ≤ q. Donner un algorithme qui calcule le produit PQ et exprimer son coût en fonction de p, q et ω.
   (b) Soit P ∈ K^(p × p) triangulaire et inversible. Soit Q ∈ K^(p × p). Donner un algorithme qui calcule la matrice X ∈ K^(p × p) telle que PX = Q, et exprimer son coût en fonction de p et ω.
2. Soient p et q dans ℕ tels que p + 2q ≤ N. Soient C_1, …, C_(p + q) des cycles de G, soient U_1, …, U_q, V_1, …, V_q des supports, et soit M ∈ K^(m × 2q) la matrice dont la colonne j est égale au vecteur d'incidence de U_j si 1 ≤ j ≤ q et à celui de V_(j − q) si q < j ≤ 2q. Pour 1 ≤ ℓ ≤ q, on suppose que les trois propriétés suivantes sont vérifiées :

• ⟨C_k, U_ℓ⟩ = 0 pour 1 ≤ k ≤ p + ℓ − 1;
• ⟨C_(p + ℓ), U_ℓ⟩ = 1;
• ⟨C_k, V_ℓ⟩ = 0 pour 1 ≤ k ≤ p.