Centrale Informatique MPI 2023Sujet, corrigé et rapport du jury

I Problème du voyageur de commerce

struct Graphe {
    int V;
    int* adj;
};

struct Graphe alloue_graphe(int V) {
    int* adj = malloc(V * V * sizeof(int));
    struct Graphe g = {.V = V, .adj = adj};
    return g;
}
void libere_graphe(struct Graphe g) {
    free(g.adj);
}

struct Chemin {
    int longueur;
    int* l_sommets;
};
struct Chemin alloue_chemin(int longueur) {
    int* l_sommets = malloc(longueur * sizeof(int));
    struct Chemin c = {.longueur = longueur, .l_sommets = l_sommets};
    return c;
}
void libere_chemin(struct Chemin c) {
    free(c.l_sommets);
}

I.A - Prise en main du problème et appartenance à NP

Figure 1 Exemple d'instance du problème du voyageur de commerce

I.B - Étude de la complexité

I.B.1) NP-complétude

Figure 2 Graphe A

• pour chaque variable y_k on crée un sommet v_k;
• on ajoute un sommet supplémentaire v_(m + 1);
• pour chaque clause C_i on ajoute une copie du graphe A, notée A_i;
• pour chaque variable y_k, on note C_(k_1), …, C_(k_ℓ) les clauses dans lesquelles y_k apparait en positif. On relie alors v_k à A_(k_1) par un arc allant de v_k vers e_p dans A_(k_1) lorsque y_k est en position p dans C_(k_1) c'est-à-dire lorsque C_(k_1) = x_(k_1, 1) ∨ x_(k_1, 2) ∨ x_(k_1, 3) et x_(k_1, p) = y_k. On relie ensuite la sortie s_p de A_(k_1) à l'entrée de A_(k_2) correspondant à la position de y_k dans C_(k_2) et ainsi de suite jusqu'au dernier dont on relie la sortie à v_(k + 1). On appelle G_k^+ le sous-graphe constitué du sommet v_k, des graphes A_(k_1), A_(k_2), …, A_(k_ℓ) et du sommet v_(k + 1), ainsi que des arcs que l'on vient d'ajouter entre eux en considérant y_k et les clauses dans lesquelles il apparait positivement ;
• on crée de même des arcs pour chaque variable y_k et chaque clause dans laquelle y_k apparait en négatif. On note G_k^−, le sous-graphe correspondant entre v_k et v_(k + 1).
  Q 9. Montrer que pour toute valuation de la formule il existe un chemin hamiltonien orienté de v_1 à v_(m + 1) dans le graphe G.
  Q 10. Montrer, en une dizaine de lignes au maximum, que pour chaque chemin hamiltonien orienté de v_1 à v_(m + 1) il existe bien une valuation.
  Q 11. En déduire que le problème du circuit hamiltonien et le problème de décision du voyageur de commerce sont NP-complets.

I.B.2) Approximation

I.C - Algorithme de Christofides

• calculer un arbre couvrant de poids minimal T de G;
• en notant I l'ensemble des sommets de degré impair dans T, calculer un couplage parfait M de poids minimum dans le sous-graphe de G induit par les sommets de I, G_(|I);
• construire H le multigraphe ayant pour sommet les sommets de G et comme arêtes les arêtes de M et celles de T;
• trouver un cycle eulérien dans H;
• transformer le cycle eulérien en circuit hamiltonien en supprimant les éventuels sommets vus plusieurs fois.

I.C.1) Arbre couvrant

struct Arete {
    int s1;
    int s2;
    int p;
};

Q 15. Écrire une fonction

struct Arete* liste_aretes(struct Graphe g);

On dispose d'une fonction

void tri_aretes(struct Arete a[], int k);

Q 16. Écrire une fonction

struct Graphe kruskal(struct Graphe g);

I.C.2) Couplage

Q 18. Écrire une fonction

int degre(struct Graphe g, int i);

Q 19. Écrire une fonction

int* sommets_impairs(struct Graphe g, int* nb_sommets);

struct Graphe graphe_induit(struct Graphe g, int nb_sommets, int* liste_sommets);
struct Graphe couplage(struct Graphe g);

I.C.3) Cycle eulérien

struct Multigraphe multigraphe(struct Graphe g1, struct Graphe g2);
struct Chemin eulerien(struct Multigraphe h);
void libere_multigraphe(struct Multigraphe h);

Q 22. Écrire une fonction

struct Chemin euler_to_hamilton(struct Chemin c);

I.C.4) Implémentation

Q 24. Écrire une fonction

struct Chemin christofides(struct Graphe g);

I.C.5) Preuve de l'approximation

II Espaces d'arbres

Arbre 1

Arbre 2

Arbre 3

Arbre 4

Arbre 5

• l'arbre 1 est un arbre binaire non raciné avec ses feuilles étiquetées ;
• l'arbre 2 est obtenu à partir de l'arbre 1 par un SPR en coupant la branche e et en la greffant sur la branche f;
• dans l'arbre 3 , où les triangles représentent des sous-arbres racinés, la branche interne e sépare 4 sous-arbres racinés A, B, C et D ;
• l'arbre 4 est obtenu à partir de l'arbre 3 par un mouvement NNI sur la branche e en échangeant les sous-arbres B et D ;
• l'arbre 5 est obtenu à partir de l'arbre 1 par un NNI sur la branche e en échangeant le sous-arbre contenant la feuille 5 et le sous-arbre contenant les feuilles 1 et 2 .
  On étudie l'espace des arbres binaires non racinés étiquetés de n feuilles B(n) suivant ces deux processus d'édition. On définit G_(NNI)(n) le graphe dont les sommets sont les arbres de B(n) et dans lequel une arête relie deux arbres si l'on peut passer de l'un à l'autre par un mouvement NNI. On définit de même G_(SPR)(n) avec les mouvements SPR. On va notamment s'intéresser à la structure de G_(NNI)(5), écrire un programme permettant de construire G_(NNI)(n) et montrer que G_(SPR)(n) est hamiltonien, c'est-à-dire qu'il possède un circuit hamiltonien.

II.A - Prise en main

II.B - Étude de G_(NNI)(5)

II.C - Construction de G_(NNI)(n)

type arbre = Feuille of int
    | Noeud of arbre * arbre ;;

Noeud (Noeud (Feuille 3,
    Noeud (Noeud (Feuille 1,
        Feuille 2),
        Feuille 4)),
    5);;

II.D − G_(SPR)(n) est hamiltonien