مسابقة دكتوراه 2025 — جامعة سعد دحلب البليدة 1 — الموضوع 02

مسابقة تخصص · Recherche Opérationnelle · المعامل: 3 · المدة: 2سا

Concours d’accès à la formation doctorale en mathématiques 2024-2025, épreuve n°02 Recherche Opérationnelle, variante n°03, Université de Blida 1, Faculté des Sciences, Département de Mathématiques, 8 février 2025, coefficient 03, durée 2h.

التمرين 1

Exercice 1 — Théorie des graphes

#graph-theory#trees#petersen-graph

Soit $G$ un graphe simple d’ordre $9$ dont chaque sommet a le degré $5$ ou $6$ . Montrer qu’il existe soit cinq sommets de degré $6$ , soit six sommets de degré $5$ .
Construire deux arbres non isomorphes à $12$ sommets ayant exactement trois sommets de degré $3$ et un sommet de degré $2$ .
Définir $\alpha(G)$ , $\omega(G)$ et $\alpha'(G)$ . a. Déterminer ces paramètres pour le graphe de la figure. b. Donner un stable maximal non maximum. c. Donner un couplage maximal non maximum.
Prouver ou infirmer les assertions sur les graphes complémentaires données dans l’énoncé.
Soit $P$ le graphe dont les sommets sont les parties à deux éléments de $\{0,1,2,3,4\}$ , deux sommets étant adjacents lorsque leur intersection est vide. a. Déterminer l’ordre, les degrés, la taille et le diamètre de $P$ . b. Dessiner $P$ . c. Déterminer sa planéité et son nombre chromatique.

◀الحل

1.

La somme des degrés vaut $45+a$ , où $a$ est le nombre de sommets de degré $6$ . Le lemme des poignées de main et l’étude du complément donnent les possibilités demandées.

2.

La somme des degrés impose huit feuilles. Les deux positions possibles du sommet de degré $2$ donnent deux arbres non isomorphes.

3.

$\alpha(G)$ est la taille d’un stable maximum, $\omega(G)$ celle d’une clique maximum et $\alpha'(G)$ celle d’un couplage maximum.

4.

Les deux premières assertions sont vraies. La troisième est fausse, par exemple avec $P_4$ .

5.

$P$ est le graphe de Petersen.

\boxed{|V|=10,\quad |E|=15,\quad d(v)=3,\quad \operatorname{diam}(P)=2}

\boxed{P\text{ est non planaire et }\chi(P)=3}

التمرين 2

Exercice 2 — Densité gamma et chaînes de Markov

#gamma-distribution#markov-chains#stationary-distribution

Soient $\theta\gt0$ et $k,\ell\ge1$ . Le couple $(X,Y)$ a pour densité

f_{X,Y}(x,y)= \begin{cases} Cx^{k-1}y^{\ell-1}e^{-\theta(x+y)},&x\ge0,\ y\ge0,\\ 0,&\text{sinon}. \end{cases}

a. Déterminer $C$ . b. Déterminer la loi marginale de $X$ . c. Pour $Z_1=X+Y$ et $Z_2=X$ , déterminer la densité conjointe de $(Z_1,Z_2)$ . d. Déterminer la loi de $Z_1$ . 2. Soit la chaîne sur $E=\{1,2,3\}$ de matrice

P=\begin{pmatrix}1-p&p&0\\\frac12&0&\frac12\\0&q&1-q\end{pmatrix}.

a. Tracer son graphe pour $p=q=\frac12$ . b. Déterminer les classes de communication. c. Discuter l’irréductibilité. d. Calculer les probabilités de transition demandées. e. Déterminer la loi issue d’une distribution initiale uniforme. f. Déterminer la distribution stationnaire pour $p=q=\frac12$ .

◀الحل

1.

\boxed{C=\frac{\theta^{k+\ell}}{\Gamma(k)\Gamma(\ell)}}

$X\sim\Gamma(k,\theta)$ et

f_{Z_1,Z_2}(z_1,z_2)=Cz_2^{k-1}(z_1-z_2)^{\ell-1}e^{-\theta z_1},

pour $0\le z_2\le z_1$ .

\boxed{Z_1\sim\Gamma(k+\ell,\theta)}

2.

La chaîne est irréductible si $p\gt0$ et $q\gt0$ . Pour $p=q=\frac12$ , la matrice est doublement stochastique.

\boxed{\pi=\left(\frac13,\frac13,\frac13\right)}