J-0
00m
00j
00h
00min
00s

Version interactive avec LaTeX compilé

Télécharger PDF

Mines Mathématiques 2 MP MPI 2024

Notez ce sujet en cliquant sur l'étoile
0.0(0 votes)
Probabilités finies, discrètes et dénombrementRéductionAlgèbre linéaire
Logo mines
🔗 Explorer
Banque
Mines
Année
2024
Filière
MP/MPI
Matière
Maths
Mines MP/MPIMines 2024MP/MPI MathsMaths 2024
2025_08_29_8b2ee14516862877423eg

É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.

Phénomènes de seuil dans les graphes

Dans ce problème, désigne un entier supérieur à 1 .
On désigne par l'ensemble des entiers compris entre 1 et .
Le groupe symétrique des permutations de est noté .
L'ensemble des matrices carrées d'ordre à coefficients réels est noté .
Le cardinal d'un ensemble fini sera noté ou .
Un graphe est un couple ( ) où :
  • désigne un ensemble fini non vide d'éléments appelés sommets du graphe
  • désigne un ensemble éventuellement vide d'éléments appelés arêtes du graphe , une arête étant un ensemble où et sont des sommets distincts de .
    Un sommet n'appartenant à aucune arête est dit isolé.
    Par convention, le graphe vide est le couple d'ensembles vides ( ).
    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 avec :
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 et à branches avec entier naturel non nul, est un graphe ( ) où est de cardinal , et est du type
On a représenté Figure 2 une étoile de centre 4 à 5 branches avec .
Figure 2 - une étoile à 5 branches
Soient et deux graphes; on dit que :
  • est inclus dans si et
  • est une copie de s'il existe une bijection de dans telle que :
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'adjacence.
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 un graphe non vide où . Indexer arbitrairement les sommets de 1 à revient à choisir une bijection (appelée aussi indexation) entre et . On pourra alors noter :
où est le sommet d'index .
Une indexation étant choisie, on définit la matrice d'adjacence du graphe associée à comme étant la matrice de dont le coefficient situé sur la ligne et la colonne est :
On remarquera d'une part que la matrice est toujours symétrique (car pour tous et entiers, 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 du graphe représenté sur la Figure 1 :
Soit une permutation du groupe symétrique et une matrice de .
Montrer que les matrices et sont semblables.
En déduire que si est un graphe non vide, et si et sont deux indexations de , alors et sont semblables.
Justifier qu'une matrice d'adjacence d'un graphe non vide est diagonalisable.
Montrer qu'une matrice d'adjacence d'un graphe non vide n'est jamais de rang 1.
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 est un graphe non vide et si et sont des indexations de , comme les matrices et sont semblables, elles ont même polynôme caractéristique (ce que l'on ne demande pas de démontrer).
On notera ce polynôme caractéristique commun et on dira que est le polynôme caractéristique du graphe .
Par convention, le polynôme caractéristique du graphe vide est le polynôme constant égal à 1 .
Soit un graphe et une copie de . Justifier que .
Soit un graphe avec . On note .
Donner la valeur de et exprimer à l'aide de .
En déduire le polynôme caractéristique d'un graphe à sommets dont les sommets non isolés forment une étoile à branches avec .
Déterminer alors les valeurs et vecteurs propres d'une matrice d'adjacence de ce graphe.
Si est un graphe non vide et si appartient à , on définit le graphe comme étant le graphe dont l'ensemble des sommets est et l'ensemble des arêtes est constitué des arêtes de qui ne contiennent pas . Voici par exemple Figure 3 un graphe et le graphe :
Figure 3 - un graphe , et le graphe
Soient et deux graphes non vides tels que et soient disjoints, c'est-à-dire tels que . Soit et soit .
On définit le graphe avec et .
Montrer que :
Déterminer le polynôme caractéristique de la double étoile à sommets, constituée respectivement de deux étoiles disjointes à et 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 est supérieur à 2 et on notera :
l'entier
  • l'ensemble des graphes de sommets
  • un réel dépendant de appartenant à l'intervalle et .
Pour tous et appartenant à avec , on note l'application de dans telle que pour tout avec :
Ainsi, est l'ensemble des graphes de dont est une arête. Réciproquement, on remarquera aussi que pour , on peut écrire
On admet l'existence d'une probabilité sur telle que les applications soient des variables aléatoires de Bernoulli de paramètre et indépendantes. On note l'espace probabilisé ainsi construit.
Autrement dit, pour un graphe donné appartenant à , la probabilité qu'une arête soit contenue dans est , et les arêtes apparaissent dans de façon indépendante.
Soit . Déterminer la probabilité de l'événement élémentaire en fonction de et .
Retrouver alors le fait que .
Dans la suite du problème on étudie la notion de fonction de seuil pour une propriété vérifiée sur une partie des graphes de .
Une fonction de seuil pour la propriété est une suite de réels strictement positifs tels que :
  • si alors la limite, lorsque tend vers , de la probabilité pour que la propriété soit réalisée vaut 0
  • si alors la limite, lorsque tend vers , de la probabilité pour que la propriété soit réalisée vaut 1 .

Partie II - Une première fonction de seuil

Section A - Deux inégalités

Soit une variable aléatoire définie sur un espace probabilisé ( ) à valeurs dans et admettant une espérance et une variance .
Montrer que .
Montrer que si , alors .
Indication : on remarquera que .

Section B - Une fonction de seuil

Quelle est la loi suivie par la variable aléatoire représentant le nombre d'arêtes d'un graphe de ?
Montrer que si au voisinage de , alors .
Montrer que si au voisinage de , alors .
En déduire une propriété et sa fonction de seuil associée.

Partie III - Fonction de seuil de la copie d'un graphe

Si est un graphe, on note (resp. ) le cardinal de (resp. ).
Soit un graphe particulier fixé. Par commodité d'écriture, on note le cardinal de le cardinal de et on suppose que et que .
On va étudier la fonction de seuil de la propriété «contenir une copie de .
On note la variable aléatoire réelle discrète définie sur l'espace probabilisé telle que pour , l'entier est égal au nombre de copies de contenues dans .
On introduit :
  • l'ensemble des copies de dont les sommets sont inclus dans :
  • pour un graphe avec , la variable aléatoire suivant une loi de Bernoulli définie par :
  • le réel défini par :
Montrer que
Soit un ensemble fixé de cardinal . On note le nombre des graphes dont l'ensemble des sommets est et qui sont des copies de .
Exprimer le cardinal de à l'aide de et en utilisant un majorant simple de , justifier que le cardinal de est inférieur à .
Exprimer à l'aide de variables aléatoires du type , et montrer que:
En déduire que si , alors .
Indication : on pourra introduire réalisant le minimum donnant .
On suppose dorénavant que .
Montrer que l'espérance vérifie :
Pour , on note :
Montrer que .
Soit ; montrer que:
Justifier que pour tous entiers naturels et vérifiant , on a:
et en déduire que pour , on a lorsque tend vers .
Montrer que où désigne la variance de .
Montrer alors que la suite est une fonction de seuil pour la propriété .
Retrouver le résultat de la question et déterminer une fonction de seuil pour la propriété «contenir une copie de l'étoile à branches» avec entier fixé supérieur à 1 .

Fin du problème

  1. 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.
Mines Mathématiques 2 MP MPI 2024 - Version Web LaTeX | WikiPrépa | WikiPrépa