DS 8 — Concours blanc : plus longue sous-suite commune et graphes d'intervalles

MP2I, année scolaire 2021-2022 — concours blanc — durée 4h, tout document ou dispositif électronique interdit.

Corrigé

Pas de corrigé disponible pour ce sujet.

Partie 1 : programmation dynamique

Plus longue sous-suite commune

En biologie, il est souvent nécessaire de comparer l'ADN provenant d'organismes différents. Un brin d'ADN est une chaîne de molécules appelées bases, où les bases sont l'adénine, la guanine, la cytosine et la thymine. En représentant chaque base par son initiale, un brin d'ADN est une chaîne de caractères sur les lettres A, G, C et T.

Par exemple, un organisme peut avoir comme ADN la chaîne

\[ S_1 = \texttt{"ACCGGTCGAGTGCGCGGAAGCCGGCCGAA"} \]

et un autre

\[ S_2 = \texttt{"GTCGTTCGGAATGCCGTTGCTCTGTAAA"} \]

Pour déterminer si deux organismes sont proches, il n'est pas suffisant d'observer les motifs contigus présents dans les deux chaînes car des mutations peuvent avoir modifié le brin en insérant des bases. Cependant, même dans ce cas, il doit être possible de retrouver une partie commune en supprimant des bases. On en déduit la définition suivante :

Définition

Soit \(s = "c_0 \dots c_{n-1}"\) une chaîne de caractères, une chaîne \(s'\) est une sous-chaîne de \(s\) s'il existe un \(p\)-uplet \((i_1, \dots, i_p)\) tel que \(s' = "c_{i_1} \dots c_{i_p}"\) et \(0 \le i_1 < i_2 < \dots < i_p \le n-1\).

Le problème qu'on se pose est de déterminer la plus longue sous-chaîne commune à deux chaînes. Ainsi, "GTCGTCGGAAGCCGGCCGAA" est la plus longue sous-chaîne commune à \(S_1\) et \(S_2\).

Caractérisation des plus longues sous-suites communes

Afin de simplifier la programmation d'une solution, on ne va pas s'intéresser à des chaînes de caractères mais à des suites finies d'éléments. On notera ici \((a_0,a_1,\dots,a_{n-1})\) une suite finie de \(n\) éléments. On adapte directement la notion précédente :

Définition

Soit \(A = (a_0, \dots ,a_{n-1})\) une suite finie et \(B\) une autre suite finie. On dit que \(B\) est une sous-suite de \(A\) s'il existe un \(p\)-uplet \((i_1, \dots, i_p)\) tel que \(B = (a_{i_1}, \dots, a_{i_p})\) et \(0 \le i_1 < i_2 < \dots < i_p \le n-1\).

Q1. Si \(A\) est une suite finie de \(n\) éléments, combien comporte-t-elle de sous-suites ? Que penser d'un algorithme qui, pour déterminer une plus longue sous-suite commune entre \(A\) et \(B\), itère sur les sous-suites de \(A\) et teste si elles sont sous-suites de \(B\) ?

Soit \(A = (a_0, \dots, a_{n-1})\) et \(i \in \range{0}{n}\), on note \(A_i = (a_0, \dots, a_{i-1})\) le \(i\)-ème préfixe de \(A\). Par définition, \(A_0\) est la suite finie vide \(()\) et \(A_n = A\).

Q2. Soient \(A = (a_0, \dots, a_{m-1})\) et \(B = (b_0, \dots, b_{n-1})\) deux suites finies et \(C = (c_0, \dots, c_{p-1})\) une plus longue sous-suite commune à \(A\) et \(B\).

Montrer que :

1. Si \(a_{m-1} = b_{n-1}\) alors \(c_{p-1} = a_{m-1} = b_{n-1}\) et \(C_{p-1}\) est une plus longue sous-suite commune à \(A_{m-1}\) et \(B_{n-1}\).
2. Si \(a_{m-1} \neq b_{n-1}\) alors \(c_{p-1} \neq a_{m-1}\) entraîne que \(C\) est une plus longue sous-suite commune à \(A_{m-1}\) et \(B\).
3. Si \(a_{m-1} \neq b_{n-1}\) alors \(c_{p-1} \neq b_{n-1}\) entraîne que \(C\) est une plus longue sous-suite commune à \(A\) et \(B_{n-1}\).

Équation de récurrence

On considère ici deux suites \(A = (a_0, \dots, a_{m-1})\) et \(B = (b_0, \dots, b_{n-1})\) et, pour \(i \in \range{0}{m}\) et \(j \in \range{0}{n}\), on note \(f(i,j)\) la longueur d'une plus grande sous-suite commune à \(A_i\) et \(B_j\).

Q3.

1. Calculer \(f(i,j)\) quand \(i = 0\) ou \(j = 0\).
2. On suppose que \(i, j > 0\) et \(a_{i-1} = b_{j-1}\). Justifier que \(f(i,j) = 1 + f(i-1, j-1)\).
3. On suppose que \(i, j > 0\) et \(a_{i-1} \neq b_{j-1}\). Justifier que \(f(i,j) = \max(f(i, j-1),f(i-1,j))\).

Résolution de la récurrence

On va résoudre la récurrence en OCaml ici.

Les sous-suites sont ainsi représentées par des 'a array.

Q4. Écrire une fonction naïve longueur_sous_suite de signature

'a array -> 'a array -> int -> int -> int

telle que l'appel à longueur_sous_suite a b i j renvoie la valeur de \(f(i,j)\) pour les suites données par \(a\) et \(b\).

On rappelle l'existence des fonctions suivantes :

• Hashtbl.create n qui crée une table de hachage de taille initiale \(n\).
• Hashtbl.find t c qui renvoie la valeur associée à la clé c dans la table et produit l'exception Not_found s'il n'y en a pas.
• Hashtbl.add t c v qui rajoute une correspondance entre la clé c et la valeur v.

Q5. Écrire une version mémoïsée de la fonction précédente.

On pourra, au choix, créer un cache en dehors de la fonction ou dans la fonction elle-même.

Tabulation

On va considérer ici une version tabulée en C.

On va représenter \(f\) dans une matrice de dimension \((m+1) \times (n+1)\). Pour simplifier, on peut considérer un tableau M de \((m+1)(n+1)\) entiers où on place \(f(i,j)\) dans M[j * (m+1) + i].

Q6. Déterminer un ordre de remplissage de \(M\) qui soit compatible avec la relation de récurrence établie au paragraphe précédent.

Q7. Écrire une fonction de prototype

int longueur_sous_suite(int *a, int m, int *b, int n);

qui renvoie la longueur d'une plus longue sous-suite commune aux deux tableaux d'entiers a de longueur m et b de longueur n.

On utilisera une tabulation selon le principe qui vient d'être exposé.

Partie 2 : problème sur les graphes

I. Graphes d'intervalles

On considère le problème concret suivant : certains cours doivent avoir lieu dans un intervalle de temps précis (par exemple de 8h à 9h50) et on cherche à attribuer une salle à chaque cours. On souhaite évidemment qu'à tout moment une salle ne puisse pas être attribuée à deux cours différents et on aimerait utiliser le plus petit nombre de salles possible.

Ce problème d'allocation de ressources (ici les salles) en fonction de besoins fixes (ici les horaires des cours) intervient dans de nombreuses situations très diverses (allocation de pistes d'atterrissage aux avions, répartition de la charge de travail sur plusieurs machines, etc.).

Représentation du problème

On modélise le problème ainsi :

• chaque besoin est représenté par un segment \([a, b]\) où \(a,b\in \N\) et \(a\leq b\) ;
• deux besoins \(I\) et \(J\) sont en conflit quand \(I\cap J\neq \emptyset\).

La donnée du problème est une suite finie \((I_0,\dots,I_{n-1})\) de \(n\) segments où \(n\in \N\).

Figure 1 — Problème (a)

Figure 2 — Problème (b)

Q8. Dans le problème \((b)\) quels sont les intervalles en conflit avec \(I_5\) ?

On représente un segment en OCaml par un couple d'entiers, la donnée du problème est représentée par un tableau d'intervalles, de type (int * int) array. Dans toute la suite, on supposera toujours que les intervalles sont des segments bien formés et donc que si (a, b) : int * int représente un intervalle alors on a a <= b et cela représente toujours le segment \([a, b]\).

Le problème \((a)\) de la figure 1 est ainsi représenté par le tableau

[|(0, 3); (1, 3); (2, 5); (4, 7);
  (6, 10); (8, 9); (11, 12)|]

On cherche à écrire une fonction conflit de type int * int -> int * int -> bool qui renvoie true si et seulement si deux segments passés en paramètres sont en conflit. Voici plusieurs versions proposées par plusieurs élèves.

let conflit1 (a, b) (c, d) = (a <= c) && (c <= b)
let conflit2 (a, b) (c, d) = (a < d) && (c < b)
let conflit3 (a, b) (c, d) = not ((b < c) || (d < a))
let conflit4 (a, b) (c, d) =
  ((a <= c) && (d <= b)) || ((c <= a) && (b <= d))

Q9. Une seule de ces versions est correcte. Laquelle ?

On suppose par la suite disposer de la version correcte de cette fonction conflit : int * int -> int * int -> bool.

Graphe simple non orienté

On rappelle qu'un graphe simple non orienté, que l'on appellera par la suite simplement graphe, est un couple \(G = (S, A)\) où

• \(S\) est un ensemble fini dont les éléments sont appelés les sommets du graphe (ici \(S\) peut être vide) ;
• \(A\) est un ensemble de paires (donc d'éléments distincts) de \(S\). Lorsque \(\{x,y\}\in A\) on dit que \(x\) et \(y\) sont reliés dans \(G\) et \(\{x,y\}\) est appelée une arête de \(G\). Les sommets reliés à un sommet \(x\) sont appelés les voisins de \(x\).

Étant donnée une énumération de \(S\) sous la forme d'une suite \((x_0,\dots,x_{n-1})\) on représente l'ensemble \(A\) en OCaml par un élément de type aretes : int list array. Ainsi pour \(i\in \{0,\dots,n-1\}\), la liste aretes.(i) contient les indices \(j\) tels que \(x_i\) soit relié à \(x_j\) dans \(G\).

Q10. Comment s'appelle cette représentation d'un graphe ?

On représente graphiquement le graphe \(G\) par un diagramme où les arêtes sont représentées par des traits entre les sommets représentés par des cercles.

Figure 3 — Un exemple de graphe

Les arêtes du graphe dont une représentation graphique est donnée à la figure 3 sont représentées en Caml par le tableau :

[|[1; 2; 3]; [0; 2; 3]; [0; 1; 3; 4]; [0; 1; 2]; [2]|]

Un tel tableau de listes d'arêtes suffit pour déterminer un graphe lorsque l'énumération des sommets est connue car on peut alors identifier un sommet à son indice. Dans la suite de ce problème on identifiera ainsi un graphe à son tableau de listes d'arêtes.

Graphe d'intervalles

Soit \(\overline{I}=(I_0,\dots,I_{n-1})\) une suite finie de segments, on appelle graphe d'intervalles associé à \(\overline{I}\) le graphe \(G(\overline{I})\)

• dont les sommets sont les segments \(I_0,\dots,I_{n-1}\)
• et où, pour \(i,j\in \{0,\dots,n-1\}\), avec \(i\neq j\) les sommets \(I_i\) et \(I_j\) sont reliés si et seulement s'ils sont en conflit.

Par exemple, le graphe d'intervalles qui correspond au problème (a) de la figure 1 admet la représentation graphique de la figure 4.

Figure 4 — Graphe d'intervalles associé au problème (a)

Q11. Donner une représentation graphique du graphe d'intervalles pour le problème \((b)\) de la figure 2.

Q12. Écrire en OCaml une fonction construit_graphe de type (int * int) array -> int list array qui étant donné un tableau segments des segments \(\overline{I}=(I_0,\dots,I_{n-1})\), énumérés dans cet ordre, renvoie la représentation des arêtes de \(G\). Quelle est sa complexité ?

II. Coloration d'un graphe

Soit \(G = (S, A)\) un graphe simple non orienté dont les sommets sont donnés par une énumération \(x_0,\dots,x_{n-1}\). On appelle coloration de \(G\) (associée à cette énumération) une suite finie d'entiers naturels \((c_0,\dots,c_{n-1})\) telle que

\[ \forall (i,j)\in \{0,\dots,n-1\}^2,\ \{x_i,x_j\}\in A\Rightarrow c_i\neq c_j \]

L'entier \(c_i\) est appelé la couleur du sommet \(x_i\) et la condition se comprend ainsi : deux sommets reliés ont des couleurs distinctes. Dorénavant, le terme couleur sera synonyme d'entier naturel. Par exemple, la suite finie \((0, 1, 2, 3, 0)\) est une coloration du graphe de la figure 3, utilisant \(4\) couleurs.

Lorsqu'une coloration utilise le plus petit nombre de couleurs distinctes possibles, on dit qu'elle est optimale. On note alors \(\chi(G)\) ce nombre minimum de couleurs, appelé le nombre chromatique de \(G\).

Remarque

En associant une salle à chaque couleur, on peut répondre au problème initial à l'aide d'une coloration de son graphe d'intervalles associé.

Q13. Déterminer \(\chi(G)\) pour les deux graphes d'intervalles associés aux problèmes \((a)\) de la figure 1 et \((b)\) de la figure 2. Justifier rigoureusement.

Couleurs disponibles

Q14. Quelle est la complexité temporelle de la fonction List.mem ?

Q15. Écrire en OCaml une fonction plus_petit_absent : int list -> int telle que l'appel plus_petit_absent liste sur une liste d'entiers naturels liste renvoie le plus petit entier naturel non présent dans liste. Justifier que cette fonction termine. Une fonction de complexité quadratique en la taille de la liste dans le pire cas convient ici.

Q16. Expliquer précisément comment on pourrait réaliser la fonction précédente avec une complexité linéaire en la taille de la liste dans le pire cas. On ne demande pas d'écrire la fonction en OCaml mais d'en décrire précisément l'idée.

Par la suite on suppose que la fonction plus_petit_absent réalise cette complexité linéaire dans le pire cas.

On considère une coloration progressive des sommets d'un graphe. Pour cela, une coloration partielle est un tableau couleurs : int array tel que couleurs.(i) contient la couleur de \(i\) s'il est coloré et \(-1\) sinon, ce qui ne pose pas de problème car les couleurs sont toujours positives.

Q17. Écrire en OCaml une fonction couleurs_voisins de signature int list array -> int array -> int -> int list telle que l'appel couleurs_voisins aretes couleurs i renvoie, avec les doublons éventuels et dans un ordre quelconque, la liste des couleurs des voisins colorés du sommet d'indice \(i\) dans le graphe décrit par aretes où le tableau couleurs décrit une coloration partielle. Quelle est sa complexité ?

Q18. En déduire une fonction couleur_disponible : int list array -> int array -> int -> int de telle manière à ce que l'appel de fonction couleur_disponible aretes couleurs i renvoie la plus petite couleur pouvant être attribuée au sommet \(i\) afin qu'il n'ait la couleur d'aucun de ses voisins dans le graphe décrit par aretes. Quelle est sa complexité ?

Colorations et cliques

Soit \(G = (S, A)\) un graphe. Un sous-ensemble \(C \subseteq S\) est appelé une clique de \(G\) lorsqu'il vérifie

\[ \forall x,y\in C,\ x\neq y\Rightarrow \{x,y\}\in A \]

La taille d'une clique est son nombre d'éléments. La taille de la plus grande clique de \(G\) (celle qui possède le plus d'éléments) est notée \(\omega(G)\).

Q19. Déterminer, sans justifier, \(\chi(G)\) et \(\omega(G)\) pour un graphe \(G = (S, A)\) avec \(|S| = n > 0\) lorsque

• (a) \(G\) ne possède pas d'arête (tous les sommets sont isolés) ;
• (b) \(G\) est un graphe complet à \(n\) sommets ;
• (c) \(G\) est un cycle à \(n\) sommets.

Q20. Comparer \(\chi(G)\) et \(\omega(G)\) pour un graphe \(G\) quelconque. Justifier.

III. Algorithme glouton pour la coloration d'intervalles

Étant donnée une liste de segments \(\overline{I}=(I_0,\dots,I_{n-1})\) de longueur \(n\geq 1\), on se propose de déterminer une coloration optimale de son graphe d'intervalles associé. On appelle coloration de \(\overline{I}\) une suite finie d'entiers naturels \((c_0,\dots,c_{n-1})\) telle que

\[ \forall (i,j)\in \{0,\dots,n-1\}^2, \ I_i\cap I_j\neq \emptyset\Rightarrow c_i\neq c_j \]

On suppose dans cette partie que les segments \(I_k=[a_k,b_k]\), pour \(k\in \{0,\dots,n-1\}\), sont énumérés dans l'ordre croissant de leurs extrémités gauches, c'est-à-dire que

\[ a_0\leq a_1\leq \dots\leq a_{n-1} \]

On propose l'algorithme suivant :

Pour \(k\) variant de \(0\) à \(n-1\), colorer l'intervalle \(I_k\) avec la plus petite couleur non encore utilisée dans la coloration des intervalles \(I_j\), avec \(0\leq j<k\), qui ont une intersection non vide avec \(I_k\).

Ainsi, l'intervalle \(I_0\) est toujours coloré avec la couleur 0, l'intervalle \(I_1\) reçoit la couleur \(0\) si \(I_0\cap I_1=\emptyset\), et la couleur \(1\) sinon, etc.

L'algorithme sur un exemple

Q21. Déterminer la coloration renvoyée par cet algorithme pour le problème \((b)\) décrit sur la figure 2, pour l'énumération des intervalles indiquée (qui respecte bien la contrainte demandée).

Coloration

Q22. Écrire en OCaml une fonction coloration : int list array -> int array telle que l'appel coloration aretes, où aretes représente les arêtes du graphe d'intervalles associé à une liste de segments triés par ordre croissant de leurs extrémités gauches, renvoie la coloration obtenue avec l'algorithme ci-dessus.

Q23. Déterminer très soigneusement la complexité de la fonction précédente en fonction du nombre \(n\) d'intervalles et du nombre \(m\) d'arêtes du graphe d'intervalles associé à la liste \(\overline{I}\).

Preuve de l'algorithme

On se propose maintenant de démontrer que l'algorithme ci-dessus fournit une coloration optimale de l'ensemble des segments. Soit \(k\) un entier entre \(0\) et \(n-1\). On suppose qu'à la \(k\)-ième étape de l'algorithme, le segment \(I_k = [a_k, b_k]\) reçoit la couleur \(c\).

Q24. Montrer que \(I_k\) a au moins \(c\) voisins d'indices inférieurs à \(k\), c'est-à-dire parmi \(I_0,\dots,I_{k-1}\).

Q25. Montrer que l'ensemble constitué de \(I_k\) et de ses voisins d'indice inférieur à \(k\) constitue une clique de taille au moins \(c+1\) dans le graphe d'intervalles associé. On pourra raisonner sur l'extrémité gauche \(a_k\) du segment \(I_k\).

Q26. En déduire que le nombre de couleurs nécessaires à une coloration de l'ensemble des segments est au moins égal à \(c+1\).

Q27. Conclure.

IV. Coloration gloutonne

L'algorithme de coloration étudié dans la partie précédente s'applique plus généralement à tout graphe étant donné une énumération \((x_0,\dots,x_{n-1})\) des sommets :

pour \(i\) allant de \(0\) à \(n-1\), on colore \(x_i\) avec la plus petite couleur qui ne soit pas utilisée par un de ses voisins déjà colorés.

On appelle coloration gloutonne d'un graphe \(G = (S, A)\) une coloration obtenue par application de l'algorithme ci-dessus, ce qui dépend uniquement de l'énumération des sommets choisie. Ainsi, si \(|S| = n\), chacune des \(n!\) façons d'ordonner les sommets du graphe induit une coloration gloutonne des sommets du graphe.

Q28. Montrer qu'une coloration gloutonne n'est pas toujours optimale. On donnera un contre-exemple sous la forme d'un graphe, d'une énumération de ses sommets, de la coloration gloutonne associée et du nombre chromatique de ce graphe (qui ne sera donc pas le même que le nombre de couleurs utilisées par la coloration gloutonne).

Q29. Montrer qu'il existe des colorations optimales qui ne sont pas des colorations gloutonnes. On donnera à nouveau un contre-exemple sous la forme d'un graphe et d'une coloration associée et on justifiera rapidement que cette coloration ne saurait être une coloration gloutonne.

L'algorithme de coloration glouton pour une énumération des sommets ne donne pas, en général, une solution optimale. Cependant, il existe toujours une énumération des sommets qui fournit une coloration gloutonne optimale.

Propriété

Soit un graphe \(G = (S, A)\). Il existe une énumération \((x_0,\dots,x_{n-1})\) des sommets de \(G\) telle que la coloration gloutonne calculée à partir de cet ordre soit optimale.

On se propose de démontrer cette proposition. Considérons une coloration valide du graphe \(G\) utilisant \(k\) couleurs numérotées de \(0\) à \(k - 1\) et notons, pour \(i \in \{0, \dots, k - 1\}\), \(C_i\) l'ensemble des sommets de \(G\) auxquels a été affectée la couleur \(i\) dans cette coloration. Considérons une énumération des sommets de \(G\) qui respecte l'ordre sur les classes \(C_i\), c'est-à-dire telle que si \(0 \leq i < j \leq k - 1\), tout sommet de couleur \(i\) est classé avant tout sommet de couleur \(j\). Considérons maintenant la coloration gloutonne obtenue avec cet ordre.

Q30. Montrer que, pour \(i \in \{0, \dots, k - 1\}\), lorsque l'algorithme glouton affecte une couleur \(c\) à un sommet \(x\) de la classe \(C_i\), cette couleur \(c\) ne peut être qu'inférieure ou égale à \(i\).

Q31. Montrer que cette coloration gloutonne utilise au plus \(k\) couleurs.

Q32. Conclure.

Il suffit donc de calculer les colorations gloutonnes associées à toutes les énumérations possibles des sommets pour trouver le nombre chromatique d'un graphe.

Q33. Que pensez-vous de cette approche ?

Trouver un ordre sur les sommets d'un graphe tel que la coloration gloutonne associée à cet ordre soit optimale est un problème difficile que l'on ne sait pas résoudre de manière efficace, du moins dans le cas général.

V. Graphes munis d'un ordre d'élimination parfait

On introduit ici la notion d'ordre d'élimination parfait, dont on montre qu'il existe toujours pour un graphe d'intervalles, et pour lequel l'algorithme glouton donne toujours une solution optimale.

Figure 5 — Un exemple de graphe admettant un ordre d'élimination parfait

Soient \(G = (S, A)\) un graphe et \((x_0,\dots,x_{n-1})\) une énumération des sommets de \(G\). Pour tout \(i\in \{0,\dots,n-1\}\), on note \(G_i=(S_i,A_i)\) où \(S_i=\{x_0,\dots,x_i\}\) et

\[ \forall k,l\in \{0,\dots,n-1\},\ \{x_k,x_l\}\in A_i\iff (k,l\leq i\ \text{ et }\ \{x_k,x_l\}\in A) \]

\(G_i\) est ainsi le graphe déduit de \(G\) en se restreignant aux sommets de \(x_0\) à \(x_i\).

Une énumération \((x_0,\dots,x_{n-1})\) des sommets de \(G\) est appelée un ordre d'élimination parfait si pour tout \(i\in \{0,\dots,n-1\}\), les voisins de \(x_i\) d'indices inférieurs à \(i\) (c'est-à-dire apparaissant avant \(i\) dans l'énumération) forment une clique (c'est-à-dire sont tous reliés).

Par exemple, dans la figure 5, l'énumération \((a,b,c,d,e,f)\) est bien un ordre d'élimination parfait alors que \((b,c,e,d,f,a)\) ne l'est pas puisque \(d\) y est précédé de \(e\) et \(c\) qui sont tous deux voisins de \(d\) sans être reliés.

Un exemple

Figure 6 — Graphe dont on demande dans la question suivante de déterminer des ordres d'élimination parfaits

Q34. Déterminer, sans justifier, parmi les exemples proposés lesquels sont bien des ordres d'élimination parfaits pour le graphe \(G\) donné par la figure 6 :

• (a) \((a,b,c,d,e,f,g,h)\).
• (b) \((a,c,b,d,f,g,h,e)\).
• (c) \((a,b,e,c,f,h,g,d)\).
• (d) \((b,c,e,f,a,g,d,h)\).

Q35. Montrer qu'il existe des graphes qui n'admettent aucun ordre d'élimination parfait. On donnera un contre-exemple sous la forme d'un graphe et l'on justifiera rapidement.

Validation d'un ordre d'élimination parfait

Dans cette partie, les fonctions devront être écrites en C. Pour cela, un graphe à \(n\) sommets et de degré maximum \(d\) sera représenté par un tableau statique g à \(n\) lignes et \(d+1\) colonnes où chaque ligne i du tableau g est un tableau g[i] contenant dans sa première case g[i][0] le degré \(d_i\) du sommet \(i\), puis, dans les cases indices \(1\) à \(d_i\), et dans un ordre arbitraire, les indices des voisins de \(i\). On n'accèdera donc pas aux cases d'indices strictement supérieurs à \(d_i\) pour un sommet \(i\), qui peuvent contenir une valeur non initialisée.

Par exemple, le graphe de la figure 3 peut être représenté par :

int g[5][4] = {
    {3, 1, 2, 3},
    {3, 0, 3, 2},
    {3, 0, 1, 3},
    {3, 0, 1, 2},
    {1, 2}
};

On remarquera qu'ici encore, une fois que la représentation d'un graphe est choisie, elle implique une énumération des sommets dont on cherchera ici à déterminer si elle correspond ou non à un ordre d'élimination parfait.

Étant donné un graphe \(G = (S ,A)\) et un ensemble \(S'\subseteq S\) de sommets de \(G\), le sous-graphe de \(G\) induit par \(S'\) est le graphe \(H = (S',A')\) où \(A'\subseteq A\) est l'ensemble des arêtes de \(G\) dont les extrémités appartiennent à \(S'\). On pourra identifier le sous-graphe \(H = (S',A')\) avec l'ensemble de sommets \(S'\).

Un graphe \(G = (S, A)\) à \(|S| = n\) sommets est représenté en C par un tableau bidimensionnel g. On représente en C un sous-graphe induit \(H = (S',A')\) d'un graphe \(G = (S, A)\) possédant \(n\) sommets par la donnée du graphe d'origine g et d'un tableau de booléens sommets à \(n\) cases dont la case \(i\) vaut true si et seulement si le sommet d'indice \(i\) est un sommet du sous-graphe induit et false sinon. On représente de même un sous-ensemble \(S' \subseteq S\) de sommets du graphe par un tableau de booléens de taille \(n\) indiquant pour chaque sommet de \(S\) sa présence dans \(S'\) ou non.

Attention

Dans toute cette partie \(n\) et \(d\) seront des constantes globales.

Q36. Écrire en C une fonction de type void voisins_inferieurs(int g[n][d + 1], int x, bool voisins_inf[n]) telle que l'appel voisins_inferieurs(g, x, voisins_inf) met à jour le tableau de booléens voisins_inf pour qu'il représente l'ensemble des voisins du sommet x d'indices strictement inférieurs à celui de x. On ne présupposera rien sur le remplissage initial du tableau voisins_inf. On garantira une complexité linéaire en \(|S| = n\).

Q37. Écrire en C une fonction de type bool est_clique(int g[n][d + 1], bool sommets[n]) telle que l'appel est_clique(g, sommets) renvoie true si et seulement si l'ensemble de sommets représenté par le tableau de booléens sommets forme une clique de g, c'est-à-dire que le sous-graphe de g engendré par ces sommets est complet. On garantira une complexité linéaire en \(|S| + |A|\). Indication : calculer en temps linéaire la taille et le nombre d'arêtes du sous-graphe.

Q38. Écrire en C une fonction de signature bool est_ordre_parfait(int g[n][d + 1]) telle que est_ordre_parfait(g) renvoie true si et seulement si l'énumération associée au graphe représenté par g est un ordre d'élimination parfait. Quelle est sa complexité ?

Ordre d'élimination parfait pour un graphe d'intervalles

Q39. Justifier rapidement qu'un graphe d'intervalles admet un ordre d'élimination parfait. Indication : on en a explicité un dans la partie III.

Ordre d'élimination parfait

Un sommet \(v\) d'un graphe \(G\) est dit simplicial lorsque l'ensemble des voisins de \(v\) dans \(G\) est une clique.

Q40. Quels sont les sommets simpliciaux du graphe de la figure 5 ?

Q41. Écrire une fonction de type bool simplicial(int g[n][d + 1], bool sg[n], int k) telle que l'appel simplicial(g, sg, k), où le sommet d'indice \(k\) est supposé appartenir au sous-graphe induit \(H\) décrit par (g, sg), renvoie true si le sommet d'indice \(k\) est simplicial dans \(H\) et false sinon. Déterminer la complexité de la fonction simplicial.

Q42. Écrire une fonction int trouver_simplicial(int g[n][d + 1], bool sg[n]) telle que trouver_simplicial(g, sg) renvoie, s'il en existe, un sommet simplicial du sous-graphe induit décrit par (g, sg) et sinon renvoie l'entier relatif \(-1\). Déterminer la complexité de cette fonction.

Q43. Montrer que si un graphe \(G = (S, A)\) possède un ordre d'élimination parfait, alors pour tout sommet simplicial \(x\) de \(G\), le sous-graphe \(H = (S', A')\) engendré par \(S' = S \setminus \{x\}\) en possède également un.

Q44. Écrire une fonction int *ordre_parfait(int g[n][d + 1]) telle que l'appel ordre_parfait(g) renvoie un ordre d'élimination parfait du graphe décrit par g, s'il en existe un et NULL sinon. Déterminer la complexité de la fonction ordre_parfait.