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

Partie 1 : Théorie des graphes (10 points = 0.5 + 0.5 + 2.75 + 2.25 + 4)

1. Soit $G$ un graphe simple d’ordre 9 tel que le degré de chaque sommet est 5 ou 6. Montrer qu’il existe ou bien 5 sommets de degré 6 ou bien 6 sommets de degré 5.

2. Construire deux arbres non isomorphes ayant chacun 12 sommets dont trois exactement sont de degré 3 et un unique sommet de degré 2.

3. Rappeler les définitions du nombre de stabilité $\alpha(G)$, du nombre de clique $\omega(G)$ et du couplage maximum $\alpha'(G)$ d’un graphe simple $G$.

Pour le graphe $G$ de la Figure 1, donner :

(a) $\alpha(G)$, $\omega(G)$ et $\alpha'(G)$, en exhibant pour chacun un exemple d’ensemble correspondant.

(b) un stable maximal qui n’est pas maximum.

(c) un couplage maximal qui n’est pas maximum.

4. Soient $G=(V(G),E(G))$ un graphe simple et $\overline{G}$ son graphe complémentaire. Prouver ou infirmer les assertions suivantes :

(a) Deux graphes sont isomorphes si et seulement si leurs complémentaires sont isomorphes.

(b) Si $G$ est non connexe alors $\overline{G}$ est connexe.

(c) Si $G$ est connexe alors $\overline{G}$ est non connexe.

5. Considérons l’ensemble $A=\{0,1,2,3,4\}$. On définit le graphe simple non orienté $P$ comme suit : les sommets sont des sous-ensembles à deux éléments de $A$ et deux sommets $x$ et sont adjacents si et seulement si .

Exemple : les sommets $\{0,1\}$ et $\{2,3\}$ sont adjacents, par contre les sommets $\{0,1\}$ et $\{1,3\}$ ne sont pas adjacents.

(a) Déterminer l’ordre, le degré de chaque sommet, la taille et le diamètre de $P$.

(b) Dessiner $P$.

(c) $P$ est-il planaire ? Quel est son nombre chromatique ?

Partie 2 : Probabilité Avancée

Exercice 1 (05 Points)

Soient $\theta\gt 0$ un nombre réel et $k,l\geq1$ deux nombres entiers et soit $(X,Y)$ un couple de variables aléatoires de densité définie par

Exercice 2 (05 Points)

Soit $(X_n)_{n\geq1}$ une chaîne de Markov sur $E=\{1,2,3\}$ de matrice de transition :