Coupes maximum dans un graphe : algorithmique, complexité et approximation
Afficher ou masquer la section
Le sujet étudie le problème de la coupe maximum dans un graphe non orienté : après des exemples introductifs, il aborde une résolution naïve exhaustive, le cas particulier des graphes bipartis, la preuve de NP-complétude par réduction depuis 3SAT via le problème STABLE, des algorithmes d'approximation (probabiliste puis dérandomisé) et un algorithme exact par séparation et évaluation, avant d'étudier l'usage d'un oracle de décision.
11. Définition d'une coupe et premiers exemplesIntroduction de la notion de coupe et de coupe maximum sur des exemples de petits graphes.
22. Premières approchesRésolution naïve par énumération de toutes les coupes, puis résolution efficace dans le cas des graphes bipartis.
33. NP-complétudePreuve que le problème de décision COUPE MAX est NP-complet, par réduction depuis STABLE puis depuis 3SAT.
44. Algorithme d'approximationConstruction d'un algorithme probabiliste garantissant une coupe de taille au moins la moitié de la coupe maximum, puis dérandomisation de cet algorithme.
55. Algorithme optimal par séparation et évaluationMise en place d'un algorithme de retour sur trace puis de branch and bound avec une heuristique d'évaluation admissible.
66. Utilisation d'un oracleReconstruction d'une coupe maximum à partir d'un oracle résolvant seulement le problème de décision associé.
Description
Sujet officiel Agrégation externe en informatique, session 2026.
Ces sujets peuvent vous intéresser
Pas encore de corrigé pour ce sujet : voici des sujets proches corrigés.
L'usage de tout ouvrage de référence, de tout dictionnaire et de tout matériel électronique (y compris la calculatrice) est rigoureusement interdit.
Il appartient au candidat de vérifier qu'il a reçu un sujet complet et correspondant à l'épreuve à laquelle il se présente.
Si vous repérez ce qui vous semble être une erreur d'énoncé, vous devez le signaler très lisiblement sur votre copie, en proposer la correction et poursuivre l'épreuve en conséquence. De même, si cela vous conduit à formuler une ou plusieurs hypothèses, vous devez la (ou les) mentionner explicitement.
NB : Conformément au principe d'anonymat, votre copie ne doit comporter aucun signe distinctif, tel que nom, signature, origine, etc. Si le travail qui vous est demandé consiste notamment en la rédaction d'un projet ou d'une note, vous devrez impérativement vous abstenir de la signer ou de l'identifier. Le fait de rendre une copie blanche est éliminatoire.
INFORMATION AUX CANDIDATS
Vous trouverez ci-après les codes nécessaires vous permettant de compléter les rubriques figurant en en-tête de votre copie.
Ces codes doivent être reportés sur chacune des copies que vous remettrez.
Coupes dans un graphe
Le problème de la coupe maximum est un problème de graphe qui trouve des applications en physique statistique, en intelligence artificielle, ou encore dans la conception de circuits imprimés.
Le sujet est découpé en six parties majoritairement indépendantes. La première introduit le concept de coupe maximum par des exemples. La deuxième propose une résolution naïve du problème, puis étudie le cas particulier des graphes bipartis. La troisième montre la NP-difficulté du problème. La quatrième présente un algorithme d'approximation avec une approche initialement probabiliste. La cinquième met en place un algorithme exact par séparation et évaluation. Enfin, la sixième et dernière partie présente le lien entre la résolution du problème de décision et du problème d'optimisation associés à la coupe maximum.
Consignes et notations
Notations. Si a et b sont des entiers, l'intervalle des entiers de a à b inclus est noté [ [a, b] ]. Pour n un entier naturel, on note ℕ_n l'ensemble des entiers de 0 à n − 1, ℕ_n = {0, 1, …, n − 1} =[ [0, n − 1] ].
La probabilité d'un événement e est notée ℙ(e). L'espérance d'une variable aléatoire X est notée 𝔼(X).
Un graphe est un couple G = (S, A) où S est un ensemble fini de sommets et A ⊆ P_2(S) un ensemble fini de paires de sommets représentant les arêtes. Dans ce sujet, tous les graphes sont non-orientés, non-pondérés, simple et sans boucle.
On identifiera une même grandeur écrite dans deux polices de caractères différentes, en italique du point de vue mathématique (par exemple n ) et en police à chasse fixe du point de vue informatique (par exemple n).
Programmation. Les questions de programmation doivent être traitées en langage Python uniquement. On accordera une attention particulière à la présentation du code, notamment à la lisibilité des indentations.
Complexité. Sans précision supplémentaire, lorsqu'une question demande la complexité d'une fonction, il s'agira de la complexité temporelle dans le pire des cas. La complexité sera exprimée sous la forme O(f(n, m)) où n et m sont les tailles des arguments de la fonction, et f une expression la plus simple possible. Dans l'ensemble du sujet, on supposera les opérations arithmétiques sur les entiers, sauf l'exponentiation, comme étant de complexité constante.
1 Définition d'une coupe et premiers exemples
Une coupe C = (S_1, S_2) d'un graphe G = (S, A) est une partition de l'ensemble S des sommets en deux parties éventuellement vides, c'est-à-dire que S_1 ∪ S_2 = S, S_1 ∩ S_2 = ∅. Une arête a ∈ A est coupée par C si elle relie les deux parties de C, c'est-à-dire si elle est de la forme a = {s_1, s_2} avec s_1 ∈ S_1 et s_2 ∈ S_2. La taille d'une coupe C, notée ‖C‖, est le nombre d'arêtes coupées par C. Une coupe C d'un graphe G est maximum s'il n'existe pas de coupe C^′ de G telle que ‖C^′‖ > ‖C‖.
Exemple. La figure 1 représente le graphe G_0 et la coupe C_0 = (S_1, S_2) où S_1 = {0, 2, 3} et S_2 = {1, 4}. Les arêtes coupées par C_0 sont représentées en pointillés. La coupe C_0 est donc de taille ‖C_0‖ = 4.
Figure 1 - Le graphe G_0 (à gauche) et la coupe C_0 du graphe G_0 (à droite).
Question 1 Soient les coupes C_1 = ({2}, {0, 1, 3, 4}) et C_2 = ({2, 3}, {0, 1, 4}) du graphe G_0. Ces coupes sont-elles maximums?
Figure 2 - Le graphe G_1.
Question 2 Donner une coupe maximum pour le graphe G_1 représenté sur la figure 2. Justifier qu'elle est bien maximum.
2 Premières approches
2.1 Approche naïve
Dans cette section, on calcule la coupe maximum d'un graphe de façon naïve en parcourant toutes les coupes possibles et en en retenant une de taille maximum au fur et à mesure. On commence par des questions préliminaires, puis on verra comment implémenter cette approche naïve.
Question 3 Dans un graphe à n sommets, combien existe-t-il de coupes? On considère que si C = (S_1, S_2) est une coupe d'un tel graphe, alors (S_2, S_1) est une coupe différente de C.
On considère que les sommets des graphes sont des entiers consécutifs à partir de 0 et on représente ces graphes par des listes de listes d'adjacence. Pour pouvoir manipuler des coupes en Python, dans l'ensemble du sujet, on les représente par des listes de booléens. Si une coupe C = (S_1, S_2) du graphe G est représentée par la liste C, alors pour tout sommet i, C[i] vaut True si et seulement si i appartient à S_1. Par exemple, le graphe G_0 est représenté par la liste [[1, 2, 3], [0, 2, 4], [0, 1, 3, 4], [0, 2, 4], [1, 2, 3]] et la coupe C_0 est représentée par la liste [True, False, True, True, False].
Question 4 Écrire une fonction cardinal_S1(C) qui prend en argument une coupe C d'un graphe et qui renvoie le nombre de sommets appartenant à S_1 dans C.
Question 5 Écrire une fonction taille(G, C) qui prend en arguments un graphe G et une coupe C de ce graphe et qui renvoie la taille ‖C‖ de C.
À présent, on souhaite implémenter l'approche naïve décrite précédemment. Pour cela, on suppose dans un premier temps que l'on dispose d'une fonction suivante(C) qui prend en argument une coupe C et qui ne renvoie rien, mais modifie la coupe pour passer à la coupe suivante de manière à ce qu'en appliquant cette fonction suffisamment de fois à la coupe [False] * n, on parcourt toutes les coupes d'un graphe de n sommets en ne passant qu'une seule fois par chaque coupe.
On suppose qu'un appel à suivante(C) lorsque C est la dernière coupe parcourue ne crée pas d'erreur et modifie C arbitrairement sans rien renvoyer.
Question 6 Écrire une fonction coupe_max_naive(G) qui prend en argument un graphe G et qui renvoie une coupe maximum en utilisant la fonction suivante.
Maintenant que l'on a implémenté la fonction principale, on cherche à implémenter la fonction suivante. On propose de commencer par une version utilisant des fonctions de conversions coupes / entiers. On verra ensuite comment implémenter une seconde version permettant de calculer directement la coupe suivante sans passer par les entiers.
Question 7 Écrire une fonction entier_vers_coupe(e, n) qui prend en arguments un entier e et un nombre de sommets n et renvoie la coupe associée, c'est-à-dire une liste de booléens res de longueur n telle que ∑_(i = 0)^(n − 1)res[i] × 2^i = e. On suppose que e ⩽ 2^n − 1 et on attend une complexité linéaire en n.
Question 8 Écrire une fonction coupe_vers_entier(C) qui prend en argument une coupe C et qui renvoie l'entier e associé à cette coupe, c'est-à-dire tel que entier_vers_coupe(e, len(C)) est égal à C. On attend une complexité linéaire en n = len(C).
Question 9 En déduire une implémentation de la fonction suivante.
Question 10 Donner, en justifiant, la complexité de coupe_max_naive qui utilise la fonction suivante implémentée dans la question précédente.
En s'inspirant de l'algorithme d'incrémentation des entiers en base 2, il est possible de passer d'une coupe à la suivante en ne parcourant que les cases à modifier.
Question 11 Écrire une fonction suivante2(C) qui prend en argument une coupe C et qui a le même effet que suivante(C) mais en ne parcourant que les cases à modifier dans C.
Question 12 Donner, en justifiant, la complexité amortie de suivante2 si on l'utilise pour parcourir toutes les coupes possibles.
Question 13 Quelle est la complexité de coupe_max_naive en utilisant la fonction suivante2 à la place de suivante?
2.2 Graphes bipartis
Dans le cas général, le problème de la coupe maximum est difficile. Dans cette section, on s'intéresse au cas particulier des graphes bipartis pour lesquels ce problème admet une résolution efficace.
Question 14 Écrire une fonction est_biparti(G) qui prend en argument un graphe G et qui renvoie :
-(False, ([], [])) si G n'est pas biparti
-(True, (X, Y)) où X et Y sont des listes de sommets de G telles que chaque sommet est dans exactement l'une des deux listes et qu'aucune arête de G ne relie deux sommets d'une même liste, sinon.
Figure 3 - Un graphe biparti G_2.
Question 15 Donner une coupe maximum du graphe biparti G_2 représenté en figure 3. Justifier la maximalité de la coupe.
Question 16 Décrire brièvement un algorithme efficace permettant de calculer une coupe maximum dans un graphe biparti quelconque.
Question 17 Écrire une fonction coupe_max_biparti(G) qui prend en argument un graphe biparti et qui renvoie une coupe maximum. On attend une complexité linéaire en |S| + |A| pour un graphe G = (S, A), mais on ne demande pas de justifier cette complexité.
On s'intéresse pour terminer cette section au cas où un graphe biparti admet une unique coupe maximum, c'est-à-dire au cas où les deux seules coupes maximum d'un graphe sont (S_1, S_2) et (S_2, S_1), pour un même S_1 et un même S_2 : la coupe maximum est unique à interversion de S_1 et S_2 près.
Question 18 Donner un graphe biparti pour lequel il n'y a pas unicité de la coupe maximum.
Question 19 Est-ce qu'un graphe biparti connexe admet nécessairement une unique coupe maximum? Justifier.
Question 20 Est-ce qu'un graphe biparti qui admet une unique coupe maximum est nécessairement connexe? Justifier.
3 NP-complétude
Dans cette partie, on souhaite montrer que le problème de la coupe maximum est un problème complexe. On s'intéresse ici à une version décisionnelle, COUPE MAX :
-instance : un graphe non orienté G = (S, A) et un entier k ∈ ℕ.
-question : est-ce que G possède une coupe C telle que ‖C‖ ⩾ k ?
On souhaite montrer que COUPE MAX est NP-complet par une réduction depuis le problème 3SAT :
-instance : une formule propositionnelle φ en 3-FNC, c'est-à-dire en forme normale conjonctive avec exactement trois littéraux par clause.
-question : est-ce que φ est satisfiable?
dont on admet qu'il est NP-complet.
3.1 NP-complétude de STABLE
Avant de se ramener au problème COUPE MAX, on montre la NP-complétude d'un autre problème de décision sur les graphes qui s'intéresse à la recherche d'un stable dans un graphe.
Étant donné un graphe non orienté G = (S, A), un stable de G est un ensemble X ⊆ S tel que deux sommets de X ne sont jamais adjacents, c'est-à-dire ∀s, t ∈ X, {s, t} ∉ A.
Le problème STABLE est le suivant :
-instance : un graphe non orienté G = (S, A) et un entier k ∈ ℕ.
-question : est-ce que G possède un stable X tel que |X| ⩾ k ?
Question 21 Montrer que STABLE ∈ NP .
Soit V = {x_1, x_2, …, x_n} un ensemble de variables et φ = ⋀_(j = 1)^m C_j une formule en 3-FNC sur V, où chaque C_j est une clause avec exactement trois littéraux. On construit le graphe G_φ = (S_φ, A_φ) de la manière suivante :
-pour chaque clause C_j = ℓ_1 ∨ ℓ_2 ∨ ℓ_3, où les ℓ_i sont des littéraux, on construit un sous-graphe avec trois sommets ℓ_1^((j)), ℓ_2^((j)) et ℓ_3^((j)) adjacents deux à deux :
-pour chaque paire x_i^((j)), ¬x_i^((j^′)) d'une variable et de sa négation apparaissant dans deux sous-graphes distincts, on rajoute une arête entre le sommet x_i^((j)) et le sommet ¬x_i^((j^′)) correspondant.
Exemple. la figure 4 représente le graphe G_(φ_0) pour φ_0 la formule définie par :
Question 22 Déterminer un modèle de φ_0, où φ_0 est la formule définie dans l'exemple précédent. À partir de ce modèle, déterminer un stable de cardinal 4 dans le graphe G_(φ_0) de la figure 4.
On considère φ = ⋀_(j = 1)^m C_j une formule propositionnelle quelconque en 3-FNC.
Question 23 Montrer que φ est satisfiable si et seulement si G_φ possède un stable de cardinal m.
Question 24 En déduire que STABLE est NP-complet.
3.2 De STABLE à COUPE MAX
On cherche maintenant à réduire le problème STABLE au problème COUPE MAX. On considère un graphe G = (S, A). À partir de G, on définit le graphe G^′ = (S^′, A^′) de la manière suivante :
-S^′ contient tous les sommets de S, ainsi qu'un nouveau sommet w, et, pour chaque arête a ∈ A, deux nouveaux sommets u_a et v_a, c'est-à-dire : S^′ = S ∪ ⋃_(a ∈ A){u_a, v_a} ∪ {w}
-tous les sommets de S^′∖{w} sont adjacents à w; de plus, pour chaque arête a = {s, t} ∈ A, A^′ contient les arêtes {s, u_a}, {u_a, v_a} et {v_a, t}, c'est-à-dire : A^′ = {{x, w}|x ∈ S^′∖{w}} ∪ ⋃_(a = {s, t} ∈ A){{s, u_a}, {u_a, v_a}, {v_a, t}}
Exemple. La figure 5 montre la construction d'un « gadget » à partir d'une arête de G.
Figure 5 - Transformation d'une arête a = {s, t} dans G en un gadget dans G^′.
Question 25 Montrer que s'il existe un stable X de cardinal k dans G, il existe une coupe C = (S_1, S_2) de cardinal k + 4|A| dans G^′, telle que X ⊆ S_1 et w ∈ S_2.
On cherche à montrer la réciproque. Pour les deux questions suivantes, on considère C =(S_1, S_2) une coupe de cardinal k + 4|A| dans G^′ et on veut montrer qu'il existe un stable X de cardinal k dans G.
Quitte à échanger les rôles, on peut supposer que w ∈ S_2. On pose Y = S ∩ S_1, c'est-à-dire l'ensemble des sommets de S_1 qui ne sont pas de la forme u_a ou v_a pour une certaine arête a.
On pose enfin A_Y = P_2(Y) ∩ A, c'est-à-dire l'ensemble des arêtes de G (pas de G^′ ) qui sont entre deux sommets de Y.
Question 27 En déduire qu'il existe un stable X ⊆ Y de G tel que |X| = k.
Question 28 En déduire que COUPE MAX est NP-complet.
4 Algorithme d'approximation
4.1 Approximation probabiliste
Soit G un graphe non orienté. On suppose que G admet une coupe maximum C^∗ de taille k^∗. On cherche à mettre en place un algorithme probabiliste qui renvoie une coupe C de taille k vérifiant k ⩾ (k^∗)/2 avec grande probabilité.
On considère l'algorithme suivant : chaque sommet est placé aléatoirement dans S_1 ou S_2 (avec probabilité 1/2 d'être dans S_1 ), et les tirages pour les différents sommets sont indépendants.
On suppose qu'on a importé le module random avec la commande suivante :
import random
La fonction randrange du module random prend en arguments deux entiers a et b et renvoie un entier tiré aléatoirement et uniformément entre a inclus et b exclu.
Question 29 Écrire une fonction coupe_proba(G) qui prend en argument un graphe G et renvoie une coupe (S_1, S_2) obtenue avec l'algorithme précédent.
Question 30 Soit C = (S_1, S_2) une coupe renvoyée par l'algorithme. Montrer que ‖C‖ a une espérance égale à (|A|)/2.
Question 31 En utilisant la fonction coupe_proba, écrire une fonction coupe_las_vegas(G), correspondant à un algorithme de type Las Vegas, qui prend en argument un graphe G et renvoie une coupe de taille supérieure ou égale à (|A|)/2.
Pour k ∈ ℕ^∗, si X est une variable aléatoire entière à valeurs dans [ [0, k] ] et d'espérance k/2, on admet l'inégalité suivante :
ℙ(X ⩾ k/2) ⩾ 1/k
Question 32 Montrer que l'espérance du temps de calcul de la fonction coupe_las_vegas, quitte à la modifier, est polynomiale en |S| et |A|.
4.2 Dérandomisation
On cherche à dérandomiser l'algorithme précédent, c'est-à-dire à le transformer en algorithme n'utilisant pas d'aléatoire, tout en gardant les mêmes garanties d'approximation. L'idée est de parcourir l'ensemble des sommets de S et de les attribuer à S_1 ou S_2 selon une heuristique à déterminer.
Le schéma général de l'algorithme est le suivant :
Entrée : Graphe G = (ℕ_n, A)
Début algorithme
Poser S_1 = ∅ et S_2 = ∅.
Pour i de 0 à n − 1 Faire
Choisir de rajouter le sommet i à S_1 ou à S_2.
Renvoyer ( S_1, S_2 )
L'étape clé est évidemment le choix d'attribution d'un sommet à S_1 ou à S_2 à la ligne 4 de l'algorithme. Pour mieux comprendre les différents états au cours de l'algorithme, pour i ⩽ n, on note S_(i, 1) et S_(i, 2) les ensembles de sommets S_1 et S_2 après avoir fait le choix pour le sommet i − 1.
On suppose que l'algorithme a été exécuté jusqu'au choix du sommet i − 1, avec i < n. On note X_i = ℕ_n∖ℕ_i l'ensemble des sommets pour lesquels aucun choix n'a été fait. On note également A_i l'ensemble des arêtes coupées par ( S_(i, 1), S_(i, 2) ) à l'étape i, et B_i l'ensemble des arêtes ayant au moins une extrémité dans X_i.
On envisage dans un premier temps de faire les choix restants de manière aléatoire et uniforme (chaque sommet a une chance sur 2 d'être attribué à S_1 et à S_2 ). On note c_i le nombre moyen d'arêtes coupées par la coupe obtenue à partir de ( S_(i, 1), S_(i, 2) ) en complétant les attributions aléatoirement.
Question 33 Montrer que c_i = |A_i| + (|B_i|)/2.
On veut remplacer les choix aléatoires par des choix déterministes qui garantissent que c_0 ⩽ c_1 ⩽ ⋯ ⩽ c_n. Pour ce faire, on note x_(i, 1) le nombre de voisins du sommet i dans S_(i, 1) et x_(i, 2) le nombre de voisins du sommet i dans S_(i, 2).
Question 34 Montrer que c_(i + 1) − c_i = {1/2(x_(i, 1) − x_(i, 2)), si le sommet i est ajouté à S_2; 1/2(x_(i, 2) − x_(i, 1)), sinon.
Question 35 En déduire une manière de faire chaque choix pour obtenir un algorithme déterministe qui est une 1/2-approximation du problème de la coupe maximum.
Question 36 Écrire une fonction coupe_approx(G) qui prend en argument un graphe G et renvoie une coupe selon l'algorithme déterministe décrit à la question précédente.
Question 37 Déterminer la complexité temporelle de la fonction coupe_approx en fonction de |S| et |A|.
5 Algorithme optimal par séparation et évaluation
On souhaite écrire un algorithme de séparation et évaluation (branch and bound) pour calculer efficacement une coupe maximum. On s'intéresse dans un premier temps à un algorithme de retour sur trace (backtracking), où on construit une solution en complétant des solutions partielles, sur le même schéma que l'algorithme d'approximation.
Pour un graphe G = (S, A) avec S = ℕ_n, on suppose qu'une solution partielle au problème est une liste de booléens C de taille i strictement inférieure à n. L'interprétation d'une telle liste est une coupe partielle C_i = (S_(i, 1), S_(i, 2)) construite de la manière suivante :
-pour s ∈ ℕ_i, C[s] vaut True, alors s ∈ S_(i, 1);
-pour s ∈ ℕ_i, C[s] vaut False, alors s ∈ S_(i, 2);
-pour s ⩾ i, il n'a pas encore été déterminé si s ∈ S_(i, 1) ou s ∈ S_(i, 2).
Question 38 Écrire une fonction retour_sur_trace(G) qui calcule une coupe maximum d'un graphe G donné en argument en utilisant un algorithme de type retour sur trace en complétant des solutions partielles au format décrit précédemment.
Question 39 Comparer la complexité temporelle de la fonction retour_sur_trace et de la fonction coupe_max_naive.
Pour une coupe partielle C_i = (S_(i, 1), S_(i, 2)), avec S_(i, 1) ∪ S_(i, 2) ⊆ ℕ_i, et pour X_i = ℕ_n∖ℕ_i, on définit les ensembles d'arêtes suivants :
-A_i est l'ensemble des arêtes entre un sommet de S_(i, 1) et un sommet de S_(i, 2), c'est-à-dire coupées par C_i (comme dans la partie précédente);
-B_i^′ est l'ensemble des arêtes entre deux sommets de X_i (à différencier de B_i de la partie précédente);
-pour s ∈ X_i, B_(i, 1)(s) (resp. B_(i, 2)(s) ) est l'ensemble des arêtes entre s et un sommet de S_(i, 1)( resp. S_(i, 2)).
On définit une heuristique d'évaluation h(C_i) par :
Question 40 Montrer que l'heuristique h est une heuristique admissible, c'est-à-dire que pour une coupe partielle C_i = (S_(i, 1), S_(i, 2)), h(C_i) est supérieur ou égale à la taille maximale d'une coupe C = (S_1, S_2) telle que S_(i, 1) ⊆ S_1 et S_(i, 2) ⊆ S_2.
Question 41 Écrire une fonction separation_evaluation(G) qui calcule une coupe maximum d'un graphe G donné en argument en utilisant un algorithme de type séparation et évaluation. Détailler l'heuristique de séparation utilisée, c'est-à-dire l'ordre dans lequel les solutions partielles sont explorées.
6 Utilisation d'un oracle
Dans cette partie, on veut savoir s'il est possible de reconstruire une coupe maximum si on sait résoudre le problème de décision COUPE MAX. On suppose disposer d'une fonction efficace oracle(G, k) qui résout le problème de décision COUPE MAX, c'est-à-dire qui prend en arguments un graphe G = (S, A) et un entier k ∈ ℕ et renvoie True s'il existe une coupe de G de taille supérieure ou égale à k et False sinon.
Question 42 Écrire une fonction taille_coupe_max(G) qui prend en argument un graphe G = (S, A) et renvoie la taille maximale d'une coupe de G. En supposant qu'un appel à oracle est en temps constant, la fonction doit avoir une complexité logarithmique en |S| + |A| et on demande de le justifier.
Question 43 Décrire en français un algorithme qui prend en argument un graphe G =(S, A) et renvoie une coupe maximum de G. En supposant qu'un appel à oracle est en temps constant, l'algorithme doit avoir une complexité polynomiale en |S| + |A|. Justifier la correction de l'algorithme.
Question 44 Écrire une fonction reconstruire_coupe_max(G) qui implémente cet algorithme.
Questions fréquentes
4 questions
Sur quels chapitres porte l'épreuve 2 d'informatique de l'agrégation externe 2026 ?
Afficher ou masquer la section
Sur quels chapitres porte l'épreuve 2 d'informatique de l'agrégation externe 2026 ?
+
Elle porte sur la théorie des graphes et l'algorithmique : coupes dans un graphe, complexité temporelle, NP-complétude par réduction, algorithmes probabilistes et dérandomisation, et algorithmes de séparation et évaluation, avec de la programmation en Python.
Les parties du sujet sont-elles indépendantes ?
+
L'énoncé précise que le sujet est découpé en six parties majoritairement indépendantes, la première introduisant la notion de coupe maximum par des exemples avant les développements algorithmiques des parties suivantes.
Quels résultats de cours faut-il connaître pour traiter ce sujet ?
+
La définition des graphes non orientés, les classes de complexité P et NP, la notion de réduction polynomiale et de NP-complétude, les bases des probabilités discrètes (espérance) et la programmation en Python.
Le sujet nécessite-t-il de programmer en Python ?
+
Oui, l'énoncé précise explicitement que les questions de programmation doivent être traitées en langage Python uniquement, avec une attention particulière portée à la lisibilité du code.
Sujet proche avec corrigéX ENS Informatique C MPI 2025X-ENS · 2025Corrigé
Même année, CAPESCAPES informatique externe 2026, épreuve 1CAPES · 2026Sujet seul
Sujet proche avec corrigéCentrale Option Informatique MP 2024Centrale · 2024Corrigé
