Centrale Informatique optionnelle MP 2024

Optimisation de réseau

a Option informatique

s .
__ MP

CONCOURS CENTRALE-SUPÉLEC 4 heures Calculatrice autorisée

Créer un réseau routier entre différentes villes, en s'autorisant des 
intersections intermédiaires, dont la longueur
totale est minimale est un problème très difficile à résoudre. Ce problème est 
une généralisation de deux pro-
blèmes pourtant faciles à résoudre : la recherche d'arbre couvrant de poids 
minimal, correspondant au cas où
il n'y à pas d'intersections intermédiaires, et la recherche de plus court 
chemin, correspondant au cas où on ne
souhaite relier que deux villes.

En 1836, un an seulement après l'apparition d'une ligne de train en Allemagne, 
Carl Friedrich Gauf s'interrogeait
dans une lettre à l'astronome Christian Schumacher sur la meilleure manière de 
relier les villes de Hambourg,
Brême, Hanovre et Brunswick par un réseau ferré.

Hamburg

Figure 1 Les quatre villes allemandes et une manière théoriquement optimale de 
les relier.

De tels arbres trouvent des applications dans la construction de réseaux 
(électroniques, routiers, ....). [ls peuvent
également apparaître dans des phénomènes naturels : des films de savon reliant 
des tiges entre deux plaques
peuvent former un arbre avec des points intermédiaires.

Figure 2 Films de savon reliant des tiges métalliques entre
deux plaques de plexiglas. Il y a trois sommets intermédiaires.

La partie I de ce problème étudie des généralités sur les arbres couvrants et 
une fonction de tri. La partie II
présente l'algorithme de Kruskal inversé pour trouver un arbre couvrant de 
poids minimal dans un graphe

! Crédits : Dutta, P., Khastgir, S. P. & Roy, A. (2010). Steiner trees and 
spanning trees in six-pin soap films. American Journal of
Physics, 78(2), 215-221.

N004/2024-05-03 18:44:51 Page 1/8 CO) 8Y-Nc-sA
connexe. La partie IIT montre la complexité du problème d'optimisation de 
réseau en se ramenant au problème
de satisfabilité. Enfin, la partie IV présente comment approcher une solution 
au problème d'optimisation en
utilisant des arbres couvrants.

Consignes aux candidates et candidats

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 Computer Modern à chasse fixe du point 
de vue informatique (par
exemple n).

Les candidates et candidats devront répondre aux questions de programmation en 
utilisant le langage OCaml.
S'ils écrivent une fonction non demandée par l'énoncé, ils devront préciser son 
rôle, ainsi que sa signature (son
type). Les candidates et candidats sont également invités, lorsque c'est 
pertinent, à décrire le fonctionnement
global de leurs programmes. On autorisera toutes les fonctions des modules 
Array et List, ainsi que les fonctions
de la bibliothèque standard (celles qui s'écrivent sans nom de module, comme 
max, incr ainsi que les opérateurs
comme EUR). Sauf précision de l'énoncé, l'utilisation d'autres modules sera 
interdite.

Lorsqu'une question de programmation demande l'écriture d'une fonction, la 
signature de la fonction demandée
est indiquée à la fin de la question. Les candidates et candidats pourront 
écrire une fonction dont la signature est
compatible avec celle demandée. Par exemple, si l'énoncé demande l'écriture 
d'une fonction int list -> int
qui renvoie le premier élément d'une liste d'entiers, écrire une fonction 'a 
list -> "a qui renvoie le premier
élément d'une liste d'éléments quelconques sera considéré comme correct.

Une annexe disponible en fin de sujet rappelle différentes fonctions en OCaml.
Définitions et notations

Pour un ensemble fini Æ, on note |F| le cardinal de Æ. On note P,(ÆE) 
l'ensemble des paires d'éléments de E,
c'est-à-dire les sous-ensembles de Æ de cardinal 2.

On définit un graphe non orienté comme un couple G = ($, A) tel que S est un 
ensemble fini d'éléments
appelés sommets et À un ensemble de paires d'éléments distincts de S appelées 
arêtes, c'est-à-dire À EUR P,(S).
S'il n'y a pas d'ambiguité, une paire {s,t} sera notée st. Si st est une arête 
du graphe, on dit que s et t sont
adjacents. Le graphe @; = ({85,81,82,S2, 84, 85}: {S082: 8082: 8084: 8189, 
8183, 8983, 8285, 8284}) est représenté
sur la figure 3.

On appelle sous-graphe de G = ($S, A) un graphe H = (X,B) tel que X C Set BC 
ANP,(X). Si X CS, on
appelle sous-graphe induit par X le graphe G[X] = (X, ANP,(X)), c'est-à-dire le 
graphe ayant X comme
ensemble de sommets et contenant toutes les arêtes de G dont les deux 
extrémités sont dans X.

Pour (s,t) EUR V*, on appelle chaîne de s à { une suite de sommets distincts 
(5,,51,...,8,) telle que sp = 5,
s, =tet pour i EUR [1,k],s;, ,s;, EUR A. On appelle cycle de G une suite de 
sommets (5,,8,,...,s,) telle que k 2 8,
(80: 84 1) est une chaîne, 5, = 84 et 5084 1 EUR À.

Un graphe est dit connexe s'il existe toujours une chaîne entre deux sommets 
distincts. Si G = ($S,A), on
appelle composante connexe de G un sous-ensemble X de S tel que G[X1] est 
connexe et pour tout s EUR S\ X,
G[X U {s}] n'est pas connexe.

Un graphe est dit un arbre (à différencier des arbres enracinés) s'il est 
connexe et ne contient pas de cycle. On
dit qu'un sous-graphe T' = (X,B) de G = (S$S, A) qu'il est un arbre couvrant si 
S = X et T'est un arbre.

On appelle graphe pondéré un triplet (5,4, f) tel que (S, A) est un graphe et f 
: À -- KR, est une fonction
qui à chaque arête associe un poids qui est un réel positif. La figure 3 
contient une représentation graphique
d'un graphe pondéré G2.

Dans un graphe pondéré G = ($S, À, f), le poids d'un sous-graphe H = (X,B, f) 
de G est la somme des poids

des arêtes qui le composent, c'est-à-dire f(H) = ÿ° f(a).
acB

SQ S3 81

Figure 3 Les graphes G. et G,

N004/2024-05-03 18:44:51 Page 2/8 (cc) BY-NC-SA
I Généralités

Q 1. Dessiner sans justifier un arbre couvrant de G; de poids minimal.

Q 2. Soit G = ($S, À) un graphe non orienté. Montrer les deux propriétés 
suivantes :

-- Si Gest connexe, alors |A] > |S]-- 1.

-- Si Gest sans cycle, alors [A[ < |S|-- 1. Q 3. En déduire l'équivalence entre les trois propriétés suivantes, pour G = ($, A) un graphe non orienté : -- G est un arbre. -- Gest connexe et |A] = |S] -- 1. -- Gest sans cycle et [A] = |S] -- 1. Pour les deux questions suivantes, on suppose que G = ($S, À, f) est un graphe pondéré tel que f est injective (toutes les arêtes ont un poids différent). Q 4. Montrer que G possède un unique arbre couvrant de poids minimal. Q 5. Soit 1* = ($S, B*) l'unique arbre couvrant de poids minimal de G. On suppose que a EUR À est une arête dont le poids est maximal dans un cycle de G. Montrer que a EUR B*. Les trois questions qui suivent ont pour objectif d'implémenter un algorithme de tri efficace. Q 6. Écrire une fonction separation telle que si 1st est une liste, alors separation 1st renvoie un couple (1lsti, 1st2) tel que chaque élément de Lst apparaît soit dans 1st1, soit dans 1st2, et les tailles de 1st1 et 1st2 diffèrent d'au plus 1. separation : 'a list -> 'a list * 'a list

Q 7. Écrire une fonction fusion telle que si 1st1 et 1st2 sont deux listes 
triées par ordre croissant, alors
fusion 1sti 1st2 renvoie une liste triée par ordre croissant contenant tous les 
éléments de 1st1 et 1st2.

fusion : 'a list -> 'a list -> 'a list

Q 8. En déduire une fonction tri_fusion qui prend en argument une liste et 
renvoie une liste triée par
ordre croissant contenant les mêmes éléments. Quelle est la complexité 
temporelle de cette fonction ? (On ne
demande pas de justifier.)

tri _ fusion : 'a list -> 'a list

IT Algorithme de Kruskal inversé

Q 9. Rappeler le principe de l'algorithme de Kruskal et sa complexité 
temporelle en fonction de |S| et |A]
lorsqu'il est appliqué à un graphe pondéré connexe G = ($, À, f).

L'algorithme de Kruskal inversé est une variante de l'algorithme de Kruskal qui 
permet de trouver un arbre
couvrant de poids minimal dans un graphe pondéré connexe. En voici une 
description en pseudo-code.

Entrées : Graphe pondéré G = ($, À, f) non orienté connexe
B + copie de À
Trier B par ordre décroissant de poids
pour «a EUR B par ordre décroissant de poids faire

si (S,B\ {a}) est connexe alors

B+ B\{a}

fin si
fin pour
renvoyer (S,B)

Algorithme 1 Algorithme de Kruskal

Q 10. Appliquer l'algorithme de Kruskal inversé au graphe G, de la figure 
figure 4. On ne demande pas la
description de l'exécution détaillée, mais simplement une représentation 
graphique de l'arbre obtenu.

N004/2024-05-03 18:44:51 Page 3/8 (cc) BY-NC-SA
Figure 4 Le graphe pondéré G;

On implémente un graphe pondéré par tableau de listes d'adjacences en OCaml, 
selon le type suivant :

type graphe = (int * float) list array

Si G=(S$S,A, f) est implémenté par un objet g de type graphe, alors :
-- l'ensemble des sommets est S = [0,n -- 1], où n = |S|:

-- gest un tableau de taille n tel que pour tout s EUR S, g.(s) est une liste 
contenant des couples (#,p) tels que
ste Aet f(st) = p.

Les listes d'adjacence ne sont pas nécessairement supposée triées par ordre 
croissant des sommets ou des poids.
Par exemple, le graphe G, de la figure 3 peut être créé par la commande :

let g2 = [II(2, 7.); (3, 6.); (1, 10.); (4, 7.)]; [(2, 5.); (0, 10.)];
L(O, 7.); (1, 5.); (3, 9.)]; ECO, 6.); (2, 9.)]; [C0, 7.)]11]

On rappelle que les opérations de comparaisons (max, min, <, >, ...) peuvent 
s'effectuer sur des uplets selon
l'ordre lexicographique.

Q 11. Écrire une fonction tri_aretes telle que si g est la représentation d'un 
graphe pondéré G = ($, À, f),
alors tri_aretes g renvoie la liste des triplets (f(st),s,t), triée par ordre 
décroissant des f(st), tels que
st E À et s < 1. Cette liste ne devra pas contenir de doublons. tri_aretes : graphe -> (float * int * int) list

Q 12. Écrire une fonction connectes telle que si g est la représentation d'un 
graphe pondéré G = ($, À, f),
(s,t) EUR S° et poids_max est un flottant, alors connectes g s t poids_max 
renvoie un booléen qui vaut true
si et seulement s'il existe un chemin de s à t dans G ne passant que par des 
arêtes dont le poids est strictement
inférieur à poids_max. La fonction devra avoir une complexité linéaire en |[S| 
+ |A] et on demande de justifier
brièvement.

connectes : graphe -> int -> int -> float -> bool

Q 13. En déduire une fonction kruskal_inverse qui prend en argument un graphe G 
= ($, À, f) et renvoie
le graphe obtenu selon le principe de l'algorithme de Kruskal inversé. On 
supposera que le graphe G donné en
argument est connexe et que la fonction de pondération f est injective.

kruskal_inverse : graphe -> graphe

Q 14. Montrer que si G est connexe, le graphe renvoyé par l'algorithme de 
Kruskal inversé appliqué à G est
un arbre couvrant de G.

Q 15. Montrer que l'arbre couvrant renvoyé par l'algorithme de Kruskal inversé 
appliqué à un graphe pondéré
connexe G est de poids minimal. On pourra commencer par traiter le cas où la 
fonction de pondération est
injective.

Q 16. Déterminer la complexité temporelle de la fonction kruskal_inverse. 
Commenter.

III Difficulté du calcul de l'arbre optimal

Dans cette partie, on présente le problème du calcul de l'arbre optimal, appelé 
arbre de Steiner, et on veut
montrer que c'est un problème difficile à résoudre.

N004/2024-05-03 18:44:51 Page 4/8 (cc) BY-NC-SA
Soit G = (S, A) un graphe non orienté connexe. On appelle arbre de Steiner de 
sommets terminaux X un
sous-graphe de G de la forme T = (Y,B) tel que T'est un arbre et X EUR Y. Les 
sommets de Y \ X sont appelés
les sommets de Steiner. Le problème de l'arbre de Steiner consiste, étant donné 
un graphe G = ($, A), un
ensemble À EUR $ et un entier k, à déterminer s'il existe un arbre de Steiner 
de sommets terminaux X ayant
moins de # sommets de Steiner.

Q 17.  Représenter graphiquement un arbre de Steiner du graphe G, de la figure 
3, ayant X = {5,,8,,s.}
comme sommets terminaux et ayant moins de 2 sommets de Steiner. Justifier qu'il 
n'en existe pas ayant moins
de 1 sommet de Steiner.

Pour montrer la difficulté de ce problème, on se ramène au problème de 
satisfaisabilité d'une formule booléenne.

On rappelle qu'un littéral est une variable ou la négation d'une variable. Une 
clause est une disjonction (V)
de littéraux. Une forme normale conjonctive (FNC) est une conjonction (A) de 
clauses. Une formule & est
dite en 3-FNC si elle est en forme normale conjonctive telle que chaque clause 
contient au plus trois littéraux.

On admet qu'étant donnée une formule propositionnelle & en 3-FNC, il est 
difficile de savoir si &© possède un
modèle, c'est-à-dire une valuation qui la satisfait.

ITIT. À --- De la satisfaisabilité au stable

Soit G = (S,A) un graphe non orienté. On dit qu'une partie X EUR S est un 
stable si c'est un ensemble de
sommets deux à deux non adjacents, c'est-à-dire si pour (s,t) EUR X2, st EUR À.

Q 18. Déterminer, en justifiant, un stable de cardinal maximal dans le graphe 
G, représenté figure 3.

Soit V = {v,,...,v,} un ensemble de variables et & une formule booléenne en 
3-FNC, de la forme 5 = À C,
j=1
où C; -- V La, les L;, étant des littéraux (de la forme v, ou --w,) et m, EUR 
[1,3].

On définit le graphe G,, = (S,,AÀ,) par:

nr
-- 5, Contient un sommet par littéral apparaissant dans une clause, 
c'est-à-dire 5, -- L) 5; OÙ :
j=1

S; -- {up | v;, apparait dans C;} U {7,0 | --v, apparait dans C;}

-- À, contient les arêtes entre chaque sommet associé à une même clause, et 
entre les sommets associés à une
variable et sa négation :

A, = {st | (s,t) EUR S7,s LE t} U {um 0) [ie flnl,) +j}

La figure 5 représente le graphe G,. pour @6 = (vu, V vs V us) À (ous Vu) À (us 
VU V ua).

AD)

UV

Figure 5 Le graphe G,, pour ÿ6 = (vs Vu V us) À (ou VU) À (us Vu V Us).
Q 19. Tracer le graphe G,, pour @, = (uv V v9) À (ug Vu Vu) À (us V uv) À (ou V 
ui Vu).

Q 20. Montrer que s'il existe un stable X de taille m dans G
comment construire un modèle de & en fonction de X.

,+ alors 4 est satisfaisable. On expliquera

Q 21. De même, montrer que si w est satisfaisable, alors il existe un stable de 
taille m dans Ge
ITI.B -- Du stable à l'arbre de Steiner
Si G = ($S,A) est un graphe non orienté, on pose G' = (S4, À) un graphe tel que 
:

-- 9,4 contient S'et un nouveau sommet par arête de @, c'est-à-dire :
Sa =SU{s, [ae A}

N004/2024-05-03 18:44:51 Page 5/8 (cc) BY-NC-SA
-- A,, contient toutes les arêtes entre deux sommet de S, et des arêtes entre 
chaque sommet s, vers chacune
des extrémités de a, c'est-à-dire :

Aa = {st]|(s,t) EUR S}U B {ss ts}

steA

Par exemple, la figure 6 est une représentation de G° où G, est le graphe de la 
figure 3.

OnC

EEE
\EX/
©

Figure 6 Une représentation de G°. Pour simplifier, on à renommé chaque sommet 
s; par 1.

Q 22. Montrer que s'il existe un stable de G de cardinal k, alors le graphe G' 
= (S4, Ac) admet un arbre
de Steiner ayant X = {s, | a EUR A} comme sommets terminaux et |S|-- k sommets 
de Steiner.

Q 23.  Réciproquement, montrer que si le graphe @&' = (S4, A) admet un arbre de 
Steiner ayant X --
{s, | a EUR A} comme sommets terminaux et £ sommets de Steiner, alors G admet 
un stable de cardinal |S|-- k.

Q 24. En déduire que si on sait trouver un arbre de Steiner ayant un nombre 
minimal de sommets de Steiner
en temps polynomial, on peut déterminer la satisfaisabilité d'une formule 
propositionnelle en 3-FNC en temps
polynomial.

IV Approximation du problème

Étant donné un graphe pondéré G = ($, À, f) et un sous-ensemble X C $, le 
problème de l'arbre de Steiner
pondéré consiste à déterminer un sous-graphe T = (Y,B, f) tel que X C Y EUR S$, 
T'est un arbre et f(T) est
minimal.

On peut voir que le problème de l'arbre de Steiner pondéré est plus difficile 
que le cas non pondéré, qui n'est
qu'un cas particulier où tous les poids sont égaux à 1. Malgré sa difficulté, 
il est possible de calculer en temps
polynomial un arbre de Steiner pondéré dont le poids est moins du double d'un 
arbre optimal.

IV.A -- Algorithme de Floyd- Warshall

L'algorithme de Floyd-Warshall est un algorithme de programmation dynamique 
permettant de calculer toutes
les distances pondérées entre deux sommets d'un graphe pondéré.

On rappelle que la représentation de G par matrice d'adjacence est une matrice 
M de dimensions n x n, où
n = |S|, telle que pour (s,t) EUR S°, M, = f(st) s'il existe st EUR À, et M,, = 
+ sinon.

En OCaml, infinity est un flottant qui se comporte comme + : plus grand que 
tous les autres flottants et
absorbant par addition ou par multiplication par un flottant strictement 
positif.

Q 25. Ecrire une fonction matrice _adjacence qui prend en argument un graphe et 
renvoie sa matrice
d'adjacence.

matrice _adjacence : graphe -> float array array

Soit G = (S,A,f) un graphe pondéré. Si EUR = (56,8,,..,s,) est une chaîne de 8, 
à s8,, le poids de c est
k

f(e) = SN f(8; 18;). Pour (s,t) EUR S°, on appelle distance de s à t, notée 
d,;(s,t) (ou d(s,t) s'il n'y a pas
i=1

d'ambiguité sur le graphe), le poids minimal d'une chaîne de s à t. S'il 
n'existe pas de telle chaîne, on pose
d(s,t) = + par convention. On remarque qu'avec une telle définition, pour s EUR 
$, d(s,s) = 0.

N004/2024-05-03 18:44:51 Page 6/8 (cc) BY-NC-SA
L'algorithme de Floyd-Warshall permet de calculer les distances des sommets 
deux à deux en considérant une

suite de matrices M), pour 4 EUR [0,n] définies de la manière suivante : pour 
(s,t) EUR S?, M l'est le poids
minimal d'une chaîne de s à t dont les sommets intermédiaires (autres que les 
extrémités) sont strictement
inférieurs à k.

Q 26. Que vaut M0) ?

Q 27. Montrer que pour 4 EUR [0,n--1]et (s,t) EUR S*, ME -- min(M MY + M).

st ? S

Q 28. Écrire une fonction floyd_warshall qui prend en argument une matrice 
d'adjacence n X n d'un graphe
G = ($S, À, f) et renvoie un couple (dist, pred) de matrices n x n telles que 
pour (s,t) EUR 5°:

-- dist.(s).(t) est un flottant correspondant à d(s,t) :

-- pred.(s).(t) est le prédécesseur de t dans un chemin de poids minimal de s à 
& si un tel chemin existe, et
--] sinon.

floyd_warshall : float array array -> float array array * int array array

Q 29. Déterminer la complexité temporelle de la fonction floyd_ warshall.

Q 30. Écrire une fonction chaine min qui prend en argument une matrice pred 
telle que décrite à la Q 28
et deux sommets s et t et renvoie une chaîne de poids minimal de s à t sous la 
forme d'une liste de ses sommets.
La fonction renverra une liste vide s'il n'existe pas de tel chemin.

chaïne_ min : int array array -> int -> int -> int list

IV.B --- Solution approchée

En considérant G = (S, A, f) un graphe pondéré non orienté connexe et X EUR S$, 
la solution approchée pour le
problème de l'arbre de Steiner est donnée par l'algorithme suivant :

-- poser À, = (X,P,(X), 9): H, est un graphe complet entre les sommets de X, 
dont les pondérations sont
données par les distances dans G (c'est-à-dire g(st) = dé(s,t)) :

-- calculer 1, = (X,B,,g) un arbre couvrant de poids minimal de A, :

-- pour chaque arête st EUR B;, \ À, la remplacer dans 7 par une chaîne de 
poids minimal dans @, en rajoutant
les sommets nécessaires. Le sous-graphe de G obtenu sera noté H, = (Y,A4,, f).

-- calculer et renvoyer T = (YY,B, f) un arbre couvrant de poids minimal de H,.
Q 31. Montrer que l'arbre T'est un arbre de Steiner de G ayant X pour sommets 
terminaux.

Q 32. Montrer que si T possède des sommets de Steiner de degré 1, leur 
suppression permet d'obtenir un
arbre de Steiner ayant X pour sommets terminaux de poids inférieur.

On pose T* un arbre de Steiner de poids minimal parmi ceux ayant À comme 
sommets terminaux.
Q 33. Montrer que f(T') < g(T), puis en déduire que f(T) < 2f(T*). On représente une partie X C S comme un tableau de booléens tab_X de taille n = |S| tel que pour 8 EUR S s E À si et seulement si tab_X.(s) vaut true. Pour créer un graphe induit par une partie X en OCamil, il est nécessaire de renuméroter des sommets, via une bijection num : X -- [0,|[X]--1]. Q 34. Écrire une fonction renumeroter qui prend en argument une partie À C S'et renvoie un tableau num d'entiers de taille n tel que pour 8 EUR $, num.(s) vaut --1 si s EUR X et num.(s) = numi(s) sinon, où num est une bijection de X -- [0,/X| -- 1] choisie arbitrairement. renumeroter : bool array -> int array

Q 35. En déduire une fonction steiner_approche qui, étant donné un graphe G = 
(S, À, f) et une partie
X EUR $ calcule un arbre de Steiner ayant À pour sommets terminaux selon 
l'algorithme présenté précédemment.
On ne demande pas de supprimer les sommets de Steiner de degré 1.

steiner_approche : graphe -> bool array -> graphe

Q 36. Déterminer la complexité temporelle de la fonction steiner_approche en 
fonction de |S|, |A] et |X|.

N004/2024-05-03 18:44:51 Page 7/8 (cc) BY-NC-SA
Annexe : rappels de programmation

Cette annexe rappelle le fonctionnement de différentes fonctions des modules 
List et Array:

-- List.iter (f: 'a -> unit) (list: 'a list) : unit fait un appel à la fonction 
f pour chaque élément
de la liste 1st. Cette fonction s'exécute en temps linéaire en la taille de la 
liste, si la fonction f se calcule en
temps constant ;

-- List.rev (ist: l'a list) : 'a list renvoie une liste contenant les mêmes 
éléments que 1st, mais dans
l'ordre inverse. Cette fonction s'exécute en temps linéaire en la taille de la 
liste :

-- Array.length (tab: 'a array) : int renvoie la longueur du tableau tab. Cette 
fonction s'exécute en
temps constant ;

-- Array.make (n: int) (x: ''a) : 'a array renvoie un tableau de longueur n 
dont toutes les cases contiennent
la valeur x. Cette fonction s'exécute en temps linéaire en n ;

-- Array.make matrix (m: int) (n: int) (x: 'a) : 'a array array renvoie une 
matrice de dimension
m x n dont toutes les cases contiennent la valeur x. Cette fonction s'exécute 
en temps linéaire en m x n.

eeorINeee

N004/2024-05-03 18:44:51 Page 8/8 (cc) BY-NC-SA