Corrigé CCINP 2026 Informatique MPI — Partie I (I.4) (Q12 à Q22) : Une 2-approximation du voyageur de commerce, en C

Sujet officiel du concours CCINP, session 2026, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Version optimisation : dans $G = (S, A, c)$ complet, dont le coût vérifie l'inégalité triangulaire $c (s, u) ⩽ c (s, t) + c (t, u)$ , trouver un cycle hamiltonien de coût minimal. Algorithme 1 : $T \leftarrow$ arbre couvrant de coût minimal de $G$ ; $L \leftarrow$ liste des sommets rencontrés lors d'un parcours en profondeur de $T$ ; $H \leftarrow$ cycle hamiltonien visitant les sommets dans l'ordre de $L$ . On note $H^{*}$ un cycle optimal et $c (E)$ le coût d'un chemin $E$ . Un sommet est ajouté à $L$ à chaque rencontre ; sur l'exemple, $L = [1, 2, 3, 2, 8, 2, 1, 4, 5, 6, 5, 7, 5, 4, 1]$ .

Q12. Quel algorithme pour l'étape 2 de l'algorithme 1 ? Sa complexité ?
Q13. Montrer $c (T) ⩽ c (H^{*})$ .
Q14. Montrer $c (L) ⩽ 2 c (H^{*})$ .
Q15. Supprimer une visite d'un sommet dans $L$ n'augmente pas le coût.
Q16. En déduire la construction de $H$ .
Q17. Conclure : l'algorithme 1 est une 2-approximation.

Structures données (sommets codés par des entiers) :


// Structure de graphe
struct Graphe_s {
    int n;            // Nombre de sommets
    int** C;          // Matrice des coûts
};
typedef struct Graphe_s Graphe;

// Structure Arbre Couvrant de coût minimal
struct ACM_s {
    int* parent;      // Tableau indiquant le parent de chaque sommet dans l'arbre
    int n;            // Nombre de sommets de l'arbre
};
typedef struct ACM_s ACM;

// Structure Cycle Hamiltonien
struct CH_s {
    int* cycle;       // Sommets dans l'ordre d'apparition dans le cycle
    int l;            // Longueur du cycle = taille du tableau cycle
};
typedef struct CH_s CH;

ACM* Recherche_ACM(Graphe* G) est fournie ; elle alloue la structure et son tableau parent de taille $n$ , rien d'autre. Le fichier texte contient n p sur la première ligne, puis $p$ lignes s t c (une arête et son coût). On dispose de fopen, fclose, fscanf.

Q18. Graphe* creer_graphe(char* nom_fichier) lit le fichier.
Q19. void dfs(ACM* a, int s, int* chemin, int* indice) : parcours en profondeur depuis la racine s, chaque sommet exploré rangé dans chemin[*indice].
Q20. CH* calcule_CH(int* chemin, int n) : le cycle, alloué et refermé.
Q21. void free_ACM(ACM* a) et void free_CH(CH* cycle).
Q22. CH* TSP2(Graphe* G) : la 2-approximation, mémoire gérée.

Corrigé

Q12. Le sujet appelle « étape 2 » le calcul de l'arbre couvrant de coût minimal $T$ (c'est la légende de la figure). On utilise l'algorithme de Kruskal : trier les arêtes par coût croissant, puis les ajouter une à une en écartant celles qui fermeraient un cycle, détecté par une structure unir & trouver. Le graphe étant complet, $∣ A ∣ = \frac{n ( n - 1 )}{2}$ : le tri coûte $O (∣ A ∣ lo g ∣ A ∣) = O (n^{2} lo g n)$ , puis les $∣ A ∣$ tests et au plus $n - 1$ unions coûtent $O (∣ A ∣ α (n))$ avec union par rang et compression des chemins, soit quasi linéaire en $∣ A ∣$ . Total : $O (n^{2} lo g n)$ . (L'algorithme de Prim avec un simple tableau des distances ferait $O (n^{2})$ , optimal ici puisqu'il faut lire les $n^{2}$ coûts.) Le jury a aussi accepté la lecture « étape 2 $=$ parcours en profondeur de $T$ » : celui-ci coûte $O (n)$ , l'arbre ayant $n$ sommets et $n - 1$ arêtes, à condition de disposer des listes de fils.

Q13. Retirons une arête $e$ quelconque de $H^{*}$ : il reste un chemin passant par tous les sommets, connexe et à $n - 1$ arêtes, donc un arbre couvrant de $G$ , de coût $c (H^{*}) - c (e) ⩽ c (H^{*})$ puisque les coûts sont positifs. $T$ étant de coût minimal parmi les arbres couvrants, $c (T) ⩽ c (H^{*}) - c (e) ⩽ c (H^{*})$ . Ce que le correcteur attend : cette minoration de l'optimum par une quantité calculable, et non une tentative de transformer $T$ en cycle.

Q14. Pour un sommet $u$ de fils $v_{1}, \dots, v_{p}$ , le parcours produit $L (u) = u \cdot L (v_{1}) \cdot u \cdot L (v_{2}) \cdot u \dots L (v_{p}) \cdot u$ (on note $u$ à la découverte puis à chaque retour d'un fils). Montrons par induction sur l'arbre que $L (u)$ commence et finit par $u$ et que $c (L (u)) = 2 c (T_{u})$ , où $T_{u}$ est le sous-arbre de racine $u$ . Pour une feuille, $L (u) = [u]$ , de coût $0 = 2 c (T_{u})$ . Sinon, chaque $L (v_{i})$ commence et finit par $v_{i}$ (hypothèse d'induction), donc les pas consécutifs de $L (u)$ sont ceux des $L (v_{i})$ plus, pour chaque $i$ , le pas $u \to v_{i}$ et le pas $v_{i} \to u$ :

$c (L (u)) = i = 1 \sum p (c (u, v_{i}) + 2 c (T_{v_{i}}) + c (v_{i}, u)) = 2 i = 1 \sum p (c (u, v_{i}) + c (T_{v_{i}})) = 2 c (T_{u}) .$

Chaque arête de $T$ est donc parcourue exactement deux fois, une à la descente et une à la remontée : $c (L) = 2 c (T) ⩽ 2 c (H^{*})$ par Q13. (Sur l'exemple, $L$ a $15 = 2 \times 7 + 1$ éléments pour les $7$ arêtes de $T$ .)

Q15. Soit $v$ un sommet qui figure plusieurs fois dans $L$ , et une de ses occurrences qui n'est pas aux extrémités de $L$ : $L = \dots, u, v, w, \dots$ On supprime cette occurrence : $L$ devient $\dots, u, w, \dots$ , ce qui est possible car $G$ est complet (l'arête ${u, w}$ existe, et si $u = w$ le pas $u \to u$ coûte $c (u, u) = 0$ ). Le coût varie de

$c (u, w) - c (u, v) - c (v, w) ⩽ 0$

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →