2024-Mines-Info-Mpi1-Corrigé

Préliminaires

Présentation du sujet

L’épreuve est composée d’un problème unique comportant 33 questions divisées en trois sections. L’objectif du problème est d’extraire un sous-graphe le plus dense d’un graphe non orienté quelconque, c’est-à-dire repérer un sous-ensemble de sommets riche en arêtes.

Le calcul d’un sous-graphe dense possède des applications considérables dans le domaine de la fouille des données : qu’il s’agisse de détection de communautés dans des réseaux sociaux, de repérage d’attaques par pollupostage (ou spamming) ou d’identification de complexes protéiques au sein de données biologiques massives pour ne citer que quelques exemples.

Dans la première section (page 1), nous résolvons un problème de minimisation de bordure dans un multigraphe orienté à l’aide d’une technique de chemins augmentants.

Dans la deuxième section (page 5), nous étudions une technique de réduction du problème de construction d’un sous-graphe le plus dense au problème de la première section. Dans la troisième section (page 8), nous étudions un algorithme d’approximation plus rapide.

Dans tout l’énoncé, un même identificateur écrit dans deux polices de caractères différentes désignera la même entité, mais du point de vue mathématique avec la police en italique (par exemple n, {n_{max}} ou {n_1}) et du point de vue informatique avec celle en romain avec espacement fixe (par exemple n, NMAX ou n1).

Travail attendu

Pour répondre à une question, il est permis de réutiliser le résultat d’une question antérieure, même sans avoir réussi à établir ce résultat.

Selon les consignes, il faudra coder des fonctions à l’aide du langage de programmation C exclusivement, en reprenant le prototype de fonction fourni par le sujet, ou en pseudo-code (c-à-d. dans une syntaxe souple mais conforme aux possibilités offertes par le langage C).

Inclure les entêtes tels que , , etc. n’est pas demandé. Quand l’énoncé demande de coder une fonction, sauf indication explicite de l’énoncé, il n’est pas nécessaire de justifier que celle-ci est correcte ou de tester que des préconditions sont satisfaites.

Le barème tient compte de la clarté et de la concision des programmes : nous recommandons de choisir des noms de variables intelligibles ou encore de structurer de longs codes par des blocs ou par des fonctions auxiliaires dont on décrit le rôle.

Lorsqu’une réponse en pseudo-code est permise, seule la logique de programmation est évaluée, même dans le cas où un code en C a été fourni en guise de réponse.

1 Entourage de plus petite bordure

Dans cette section, nous travaillons dans un multigraphe orienté, c’est-à-dire un couple {(W,F,\mu)} où W est un ensemble fini, appelé ensemble de sommets, F est une partie de {W\times W} , appelée ensemble d’arcs, et {\mu:F\to} {\mathbb N^*} est une application, appelée multiplicité des arcs.

Les démonstrations ou justifications pourront utiliser la notion de multi-ensemble sans formalité excessive.

L’intersection, notée {\cap}, se calcule en considérant le minimum des multiplicités des éléments ; l’union disjointe, notée {\sqcup}, se calcule en considérant la somme des multiplicités des éléments ; le cardinal se calcule en sommant toutes les multiplicités.

1.1 Réseaux

Définitions : Nous appelons réseau tout quintuplet H = {(W,F,\mu,s,t)} tel que — W est un ensemble fini, appelé ensemble de sommets, — F est un sous-ensemble de couples de {W\times W} , appelé ensemble d’arcs, — {\mu} est une application {F\to} {\mathbb N^*}, l’entier naturel {\mu(e)} étant appelé la multiplicité de l’arc e, — s est un sommet particulier de W , appelé la source, — t est un sommet particulier de W , appelé le puits.

Indication C : Par convention, nous numérotons les sommets d’un réseau H = {(W,F,\mu,s,t)} par les entiers entre 0 et n + 1, où n + 2 est le cardinal de W . La source s porte le numéro 0 ; le puits t porte le numéro n + 1. Nous préparons deux fichiers, network.h et network.c.

Le premier fichier contient les déclarations suivantes.

Le second fichier contient initialement les définitions suivantes et sera complété par les fonctions de la section 1.

Pour tout couple {(u,v)\in W\times W} , le champ mu[u][v] de la variable gobale H vaut 0 si (u, v) n’est pas un arc du réseau et vaut {\mu((u,v))} si (u, v) est un arc.

Nous utilisons le terme chemin pour signifier systématiquement un chemin simple dans le graphe orienté (W, F ), c’est-à-dire une suite d’arcs {(e_1,\ldots,e_t)} de {F} distincts qui se succèdent. Le sommet initial d’un chemin s’appelle la source, le sommet final s’appelle le puits.

1.2 Déconnexion de la source et du puits

Définition : Nous disons qu’un ensemble de chemins {\Pi=\{\pi_1,\ldots,\pi_k\}} de source commune s et de puits commun t est réalisable dans le réseau H = {(W,F,\mu,s,t)} si, pour tout arc {e\in F} , les chemins de {\Pi} utilisent moins de {\mu(e)} fois l’arc e, autrement dit {\forall e\in F,\quad\operatorname{Card}\{j\in\{1,\ldots,k\}:e\in\pi_j\}\le\mu(e).} Définition : Étant donné un ensemble réalisable de chemins {\Pi=\{\pi_1,\ldots,\pi_k\}} de source commune s et puits commun t dans un réseau H = {(W,F,\mu,s,t)}, nous appelons réseau résiduel de H par rapport à {\Pi}, et nous notons Res(H, {\Pi}), le réseau obtenu à partir de H en effectuant, pour tout indice j compris entre 1 et k et pour tout arc {e=(u,v)\in\pi_j}, la suppression d’une occurence de l’arc e et l’ajout d’une occurence de l’arc opposé e = (v, u).

1.3 Optimalité

Définition : Soit H = {(W,F,\mu,s,t)} un réseau et S un sous-ensemble de sommets de W . Nous appelons bordure, et notons {\partial S}, l’ensemble d’arcs allant de S vers son complémentaire : {\partial S=\{(u,v)\in F:u\in S,\ v\notin S\}} .

Nous étendons la notion de multiplicité à des ensembles d’arcs en posant : {\mu(\partial S)=\sum_{e\in\partial S}\mu(e).}Définition : Nous appelons entourage dans le réseau H = {(W,F,\mu,s,t)} tout sous-ensemble de sommets {S\subseteq W} contenant la source s mais pas le puits t.

Nous fixons pour les quatre prochaines questions un ensemble réalisable {\Pi_0} de {k_0} chemins dans un réseau {H} tel que, dans le réseau résiduel {\operatorname{Res}(H,\Pi_0)}, il n’existe plus aucun chemin entre la source {s} et le puits {t}.

Nous notons {S_0} l’entourage dans {H} composé des sommets accessibles dans {\operatorname{Res}(H,\Pi_0)} depuis la source {s}.

Définition : Nous disons qu’un entourage S est de plus petite bordure s’il minimise la multiplicité {\mu(\partial S)}. Nous notons {\sigma(H)} la multiplicité de la bordure d’un tel entourage.

2 Algorithme de Goldberg

2.1 Densité d’un graphe

Pour tout ensemble fini {X}, la notation {\binom X2} désigne l’ensemble des paires (non ordonnées) à valeur dans {X}, c’est-à-dire l’ensemble {\binom X2=\{\{u,v\}:(u,v)\in X^2,\ u\ne v\}.} Définition : Un graphe non orienté est un couple {G=(V,E)} où {V} est un ensemble fini, appelé ensemble de sommets, et {E\subseteq\binom V2} est un ensemble de paires, appelé ensemble d’arêtes.

Pour tout ensemble de sommets {X\subseteq V}, nous notons {G_X=(X,E_X)} le graphe {G_X=(X,E\cap\binom X2)}, appelé graphe induit par {X} sur {G}.

Indication C : Par convention, nous numérotons les sommets de tout graphe non orienté G = (V, E) par les entiers entre 1 et n, où n est le cardinal de V .

Nous représentons un graphe par un tableau de listes d’adjacence doublement chaînées en adoptant les déclarations de type suivantes.

Le champ neighbours est un tableau alloué dynamiquement de longueur n + 1 et dont la première case n’est pas utilisée.

Chaque arête est stockée sous forme de deux arcs.

Définition : Nous notons {\deg_G(v)} le degré d’un sommet {v} dans le graphe non orienté {G=(V,E)} : {\deg_G(v)=|\{u\in V:\{u,v\}\in E\}|=\sum_{\substack{u\in V\\[8pt]\{v,u\}\in E}}1.}

Définition : Nous appelons densité du graphe G = (V, E) le rapport {\delta(G)=\frac mn} où n est le cardinal de V et m est le cardinal de E.

Définition : Le problème d’optimisation du sous-graphe le plus dense d’un graphe non orienté {G} consiste à trouver un ensemble de sommets non vide {X} tels que la densité {\delta(G_X)} du sous-graphe induit {G_X=(X,E_X)} est maximale et calculer cette densité maximale {\rho(G)=\max_{\substack{X\subseteq V\\[8pt]X\ne\varnothing}}\delta(G_X).}

2.2 Oracle pour le problème de décision

Nous nous intéressons au problème de décision suivant : Étant donnés un graphe non orienté {G} à {n} sommets et un entier naturel {r}, existe-t-il un sous-graphe induit {G_X=(X,E_X)} de densité {\delta(G_X)} strictement supérieure au seuil {r/n^2} ? Autrement dit, a-t-on {\rho(G)>r/n^2} ?

Définition : Étant donnés un graphe non orienté G = (V, E) avec n sommets et m arêtes ainsi qu’un entier naturel r, nous appelons réseau associé au graphe G et au seuil r le réseau H = {(W,E,\mu,s,t)} où (α) L’ensemble W est la réunion {W=V\cup\{s,t\}}, les sommets source s et puits t étant de nouveaux sommets n’appartenant pas à V . (β) L’ensemble d’arcs F comprend : — pour tout sommet {v\in V} , un arc (s, v), de multiplicité {mn^2}. — pour toute arête {\{u,v\}\in E}, un arc (u, v) et un arc (v, u), de multiplicité {n^2}. — pour tout sommet {u\in V} , un arc (u, t), de multiplicité {mn^2-n^2\deg_G(u)+2r}.

2.3 Recherche dichotomique

Nous considérons l’ensemble de couples d’entiers {\Delta=\{(m^{\prime},n^{\prime})\in\mathbb N^2:0\le m^{\prime}\le m,\ 1\le n^{\prime}\le n\}.}

3 Algorithme de Charikar

Dans le cadre d’un compromis entre temps d’exécution et justesse du calcul d’optimisation, nous nous intéressons à l’algorithme suivant. Algorithme 1 : Recherche gloutonne d’une densité élevée Entrées : Graphe G = (V, E). Sorties : Sous-graphe induit à grande densité

3.1 Analyse d’un facteur d’approximation

Définition : Nous appelons orientation d’un graphe non orienté {G=(V,E)} tout graphe orienté {\widehat G=(V,\widehat E)} tel qu’il existe une bijection {\omega:E\to\widehat E} avec {\omega(\{u,v\})=(u,v)} pour tout arc {(u,v)\in\widehat E}. Le degré entrant d’un sommet {v} dans un graphe orienté {\widehat G=(V,\widehat E)} est {\deg^-_{\widehat G}(v)=\operatorname{Card}\{u\in V:(u,v)\in\widehat E\}=\sum_{\substack{u\in V\\[8pt](u,v)\in\widehat E}}1.}

Nous exécutons l’algorithme 1 sur un certain graphe non orienté G. Dans les questions qui suivent, nous numérotons les sommets de G selon la même numérotation que celle de l’algorithme. Nous notons {\omega_0} la bijection qui oriente l’arête {\{v_i,v_{i^{\prime}}\}} dans le sens {(v_{\min(i,i^{\prime})},v_{\max(i,i^{\prime})})} et {\widehat G_0} l’orientation associée.

Autrement dit, nous orientons toute arête, au moment de sa suppression, vers le sommet incident qui a conduit à sa suppression.

3.2 Implémentation optimale