Mines Maths 2 MP-MPI 2024

A2024 --- MATH II MP

Cm

Concours commun

Mines-Ponts

ÉCOLE DES PONTS PARISTECH,
ISAE-SUPAERO, ENSTA PARIS,
TÉLÉCOM PARIS, MINES PARIS,
MINES SAINT-ÉTIENNE, MINES NANCY,
IMT ATLANTIQUE, ENSAE PARIS,
CHIMIE PARISTECH - PSL.

Concours Mines-Télécom,
Concours Centrale-Supélec (Cycle International).

CONCOURS 2024
DEUXIÈME ÉPREUVE DE MATHÉMATIQUES

Durée de l'épreuve : 4 heures

L'usage de la calculatrice et de tout dispositif électronique est interdit.

L'énoncé de cette épreuve comporte 8 pages de texte.

Si, au cours de l'épreuve, un candidat repère ce qui lui semble être une erreur
d'énoncé, il le signale sur sa copie et poursuit sa composition en expliquant 
les
raisons des initiatives qu'il est amené à prendre.

Les sujets sont la propriété du GIP CCMP. Ils sont publiés sous les termes de 
la licence
Creative Commons Attribution - Pas d'Utilisation Commerciale - Pas de 
Modification 3.0 France.
Tout autre usage est soumis à une autorisation préalable du Concours commun 
Mines Ponts.

Phénomènes de seuil dans les graphes

Dans ce problème, n désigne un entier supérieur à 1.

On désigne par [1,n] l'ensemble des entiers compris entre 1 et n.

Le groupe symétrique des permutations de ]1,n] est noté S,.

L'ensemble des matrices carrées d'ordre n à coefficients réels est noté M,(R).
Le cardinal d'un ensemble fini E sera noté card(Æ) ou |E|.

Un graphe G est un couple ($, À) où :

-- S désigne un ensemble fini non vide d'éléments appelés sommets du graphe G

-- À désigne un ensemble éventuellement vide d'éléments appelés arêtes du graphe
G, une arête étant un ensemble {s. s' } où s et s' sont des sommets distincts 
de S.

Un sommet n'appartenant à aucune arête est dit isolé.
Par convention, le graphe vide est le couple d'ensembles vides (S, &).

On peut représenter un graphe non vide dans un plan à l'aide :

-- de disques schématisant les sommets du graphe

-- de segments reliant ces disques pour les arêtes du graphe.

Par exemple, on a représenté sur la FIGURE 1, le graphe G = ($S, À) avec :

S=T[19] et A = {{12},{1,5},{1,6},{2,3},{2,0}.{2.8}}

FIGURE 1 --- un graphe à 9 sommets et 6 arêtes

On remarquera que les arêtes sont constituées de deux sommets distincts, ce qui
interdit la présence de «boucles» reliant un sommet à lui-même.
De plus, une même arête ne peut être présente plusieurs fois dans un graphe.
Un type de graphe utilisé dans ce problème est l'étoile.
Une étoile de centre s et à d branches avec d entier naturel non nul, est un 
graphe

(S, À) où S -- {s. S1,59,..., sa} est de cardinal d + 1, et À est du type

AZ {{ss}{ss}..,{ss})

On a représenté FIGURE 2 une étoile de centre 4 à 5 branches avec S -- {1 3,4, 
5,6, 8}.

FIGURE 2 --- une étoile à 5 branches

Soient G = (5, A) et G = (S", 4') deux graphes ; on dit que :
-- Gest inclus dans G si SC Set A CA

-- G' est une copie de G s'il existe une bijection © de S" dans $ telle que :

V(sL)ES xs {s',1'} E A {o(s'),o(f')} EUR A

Par exemple, le graphe de la FIGURE 1 contient plusieurs copies d'étoiles à une 
branche
(correspondant aux segments), plusieurs copies d'étoiles à deux branches, mais 
aussi une
copie d'une étoile à 3 branches (de centre 1) et une copie d'une étoile à 4 
branches (de

centre 2).

Dans une première partie, on étudie quelques propriétés algébriques des 
matrices d'ad-

jacence.
On introduit ensuite la notion de fonction de seuil en probabilité des graphes 
aléatoires.

Les deux parties qui suivent la première partie sont indépendantes de celle-ci, 
et sont
consacrées à l'étude de deux exemples.
Partie I - Quelques propriétés algébriques des
matrices d'adjacence

Soit G = (S, À) un graphe non vide où |S| = n. Indexer arbitrairement les 
sommets
de 1 à n revient à choisir une bijection (appelée aussi indexation) © entre 
]1,n] et S.

On pourra alors noter :
S = {a(1),o(2).....a(n)}

où o(i) est le sommet d'index .

Une indexation © étant choisie, on définit la matrice d'adjacence MG, du graphe 
G
associée à o comme étant la matrice de M,(R) dont le coefficient situé sur la 
4° ligne
et la 7° colonne est :

1 si{o(i),o(j)} EUR À
ch = À

Ü sinon

On remarquera d'une part que la matrice MG, est toujours symétrique (car pour 
tous
i et j entiers, {i, 1 } -- { 1. i}) et d'autre part que les termes de la 
diagonale sont tous

nuls (pas de boucle dans un graphe).
Voici par exemple la matrice d'adjacence Mia du graphe G représenté sur la F1-
GURE 1 :

010011000
floiooooii
010000000
000000000
Maia = | 1000000000
100000000
000000000
(0106000000
010000000
Soit p une permutation du groupe symétrique $, et M -- (mi; )1 Montrer que les matrices M et (m,(),p(5))1 Justifier qu'une matrice d'adjacence d'un graphe non vide est 
diagonalisable.
3 > Montrer qu'une matrice d'adjacence d'un graphe non vide n'est jamais de 
rang I.
4 > Montrer qu'une matrice d'adjacence d'un graphe dont les sommets non isolés

forment un graphe de type étoile est de rang 2 et représenter un exemple de 
graphe
dont la matrice d'adjacence est de rang 2 et qui n'est pas du type précédent.

Si G = ($S, A) est un graphe non vide et si o et o' sont des indexations de $, 
comme
les matrices MG, et MG sont semblables, elles ont même polynôme caractéristique 
(ce
que l'on ne demande pas de démontrer).
On notera Ya ce polynôme caractéristique commun et on dira que ya est le 
polynôme
caractéristique du graphe G.

Par convention, le polynôme caractéristique du graphe vide est le polynôme 
constant
égal à 1.

5 > Soit G un graphe et G" une copie de G. Justifier que Ya = x.

n--1

6 > Soit G = (S, A) un graphe avec [S| = n > 2. On note YG(X) = X"+ 9 a; X*.
k=0

Donner la valeur de a,_1 et exprimer a,_2 à l'aide de |A|.

7 > En déduire le polynôme caractéristique d'un graphe à n sommets dont les 
sommets
non isolés forment une étoile à d branches avec 1  Montrer que :
XG -- XG1 À XG2a -- XGi\s1 À XGo2\s2

9 > Déterminer le polynôme caractéristique de la double étoile à di + d2 + 2 
sommets,
constituée respectivement de deux étoiles disjointes à d; et d2 branches, à qui 
l'on
a ajouté une arête supplémentaire reliant les deux centres des deux étoiles.

Quel est le rang de la matrice d'adjacence de cette double étoile ?

Dans toute la suite de ce problème, on suppose que n est supérieur à 2 et on 
notera :

-- N l'entier F,) -- n(n _ 1)

2
-- (Q, l'ensemble des graphes de sommets S = [1,n]

-- p, un réel dépendant de n appartenant à l'intervalle ]0, 1! et qh = 1 -- ph.
Pour tous à et j appartenant à S = [1,n] avec à £ j, on note XY;,, 
l'application de
(), dans {0, 1} telle que pour tout G EUR Q, avec G = (5, À) :
1 si{i,j}EURA
0 si{ij}#A
Ainsi, (X4,;, = 1) -- {G EUR O, | Xy,(G) -- 1} est l'ensemble des graphes de Q, 
dont

{i, j} est une arête. Réciproquement, on remarquera aussi que pour G = (S, A), 
on peut

{(G}= (Aug =D ( COEg =0). (1)

{(5,1}EURA {,1}EA

X{,5}(G) =

On admet l'existence d'une probabilité P sur (Q,,. P(Q)) telle que les 
applications
X 5,5, Soient des variables aléatoires de Bernoulli de paramètre p, et 
indépendantes. On
note Ën -- (Q,. P(Q,), P) l'espace probabilisé ainsi construit.

Autrement dit, pour un graphe G donné appartenant à (,, la probabilité qu'une
arête {i, 1 } soit contenue dans G est p,, et les arêtes apparaissent dans G de 
façon
indépendante.

10 & Soit G = ($S, A) EUR Q,. Déterminer la probabilité P({G }) de l'événement 
élémen-
taire {G} en fonction de ph, qn, N et a = card(A).

Retrouver alors le fait que P(Q,) = 1.
Dans la suite du problème on étudie la notion de fonction de seuil pour une 
propriété
P, vérifiée sur une partie des graphes de (,.

Une fonction de seuil pour la propriété P, est une suite (t:)4>2 de réels 
strictement
positifs tels que :

-- si ph -- O(t,) alors la limite, lorsque n tend vers +0o, de la probabilité 
pour que la
propriété P, soit réalisée vaut 0

-- Si Én -- 0(ph) alors la limite, lorsque n tend vers +00, de la probabilité 
pour que la
propriété P, soit réalisée vaut 1.

Partie II - Une première fonction de seuil

Section À - Deux inégalités
Soit X une variable aléatoire définie sur un espace probabilisé (Q, 4, P) à 
valeurs dans
N et admettant une espérance E(X) et une variance V(X).

11 > Montrer que P(X > 0) < E(X). 12 > Montrer que si E(X) £ 0, alors P(X = 0) < Indication : on remarquera que (X = 0) EUR (IX -- E(X)| > E(X)).

Section B - Une fonction de seuil

13 > Quelle est la loi suivie par la variable aléatoire À, représentant le 
nombre d'arêtes
d'un graphe de (,, ?

Il
14 > Montrer que si p, -- o(--) au voisinage de +oco, alors lim P(4, > 0) = 0.

n? n-- +00
. 1 ,
15 > Montrer que si -- -- o(p,) au voisinage de +00, alors lim (A, > 0) = 1.
n n CO

16 > En déduire une propriété P, et sa fonction de seuil associée.
Partie III - Fonction de seuil de la copie d'un
graphe

Si G = ($S, A) est un graphe, on note sG (resp. aa) le cardinal de S' (resp. À).

Soit Go -- (So, Ao) un graphe particulier fixé. Par commodité d'écriture, on 
note
So = Sc, le cardinal de 55, ao = ag, le cardinal de À, et on suppose que s9 > 2 
et que
(O7S) > 1.

On va étudier la fonction de seuil de la propriété P,, : «contenir une copie de 
Go.

On note XY la variable aléatoire réelle discrète définie sur l'espace 
probabilisé EUR, telle
que pour G EUR (,, l'entier X°(G) est égal au nombre de copies de G) contenues 
dans G:
On introduit :

-- l'ensemble C des copies de Go dont les sommets sont inclus dans [1, n] :

Co = {H | H est une copie de Go et H = (Sy, An) avec Sx © [1,n]}

-- pour un graphe H = (Sy, An) avec Sy EUR [1,n], la variable aléatoire suivant 
une
loi de Bernoulli X 7 définie par :

1 SHCG
VE EC An(G) = L sinon
-- Je réel wo défini par :
..... SH
2
ax 21
17 > Montrer que
E(X x) = pr".

18 & Soit S, un ensemble fixé de cardinal 59. On note EUR le nombre des graphes 
dont
l'ensemble des sommets est Sf et qui sont des copies de Go.

Exprimer le cardinal de C à l'aide de & et en utilisant un majorant simple de 
co,
justifier que le cardinal de C est inférieur à n°.

19 > Exprimer XY à l'aide de variables aléatoires du type Xy, et montrer que :

E(X,) = à P(HCG) En déduire que si p, -- o(n "}), alors lim P(X£ > 0) = 0.

n-- +00

Indication : on pourra introduire À, EUR Go réalisant le minimum donnant wo.
/ 0 :
On suppose dorénavant que AUS (n Pn) -- +00.

21 > Montrer que l'espérance E((X9)?) vérifie :

E((X}))= D P(HUHCG)= D pion.
(H,H')eCé (H,H')eCé

Pour k EUR [0, 5], on note :
= >  P(HUH CG).

(H,H')eCé
SHn!K
2
22 > Montrer que Yo < (E(X?)) 23 > Soit k& EUR ]1,50] ; montrer que :

So\ {nn -- So ne
Dr < >» nl L Ja Dn 0
HECo S0 --

24 > Justifier que pour tous entiers naturels q et r vérifiant 1 < q  Montrer que lim (An)

-- 0 où V(X®?) désigne la variance de X£.
26 > Montrer alors que la suite (k7"),>2 est une fonction de seuil pour la 
propriété P,.
27 > Retrouver le résultat de la question 16 > et déterminer une fonction de 
seuil pour la

propriété «contenir une copie de l'étoile à d branches» avec d entier fixé 
supérieur
à 1.

FIN DU PROBLÈME