مسابقة دكتوراه 2019 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — الموضوع 04

مسابقة عامة · الرياضيات · المعامل: 1

Concours d'accès à la Formation Doctorale Mathématiques Appliquées, USTHB, spécialités OStoch, ROM, ROMaD — Épreuve générale (26 Octobre 2019, 1h30, coefficient 1).

التمرين 1

Exercice 1 — Programmation linéaire paramétrique

#linear-programming#parametric-programming#duality#graphical-solution

On considère le programme linéaire suivant :

(P(t)) \begin{cases} \min Z = -3x_1 + 4x_2 - 2x_3 + tx_4 \\\\ x_1 + x_2 - x_3 - x_4 \le 8 \\\\ x_1 - x_2 + x_3 - x_4 \le 4 \\\\ x_1,x_2,x_3,x_4 \ge 0. \end{cases}

Écrire ce problème sous forme standard en ajoutant deux variables d'écart $x_5$ et $x_6$ . Soit $Q(t)$ le problème obtenu.
Résoudre $Q(t)$ en fonction de $t$ .
Écrire le problème dual $D(t)$ de $Q(t)$ .
Résoudre $D(t)$ graphiquement. Commenter.

◀الحل

On ajoute $x_5,x_6 \ge 0$ pour transformer les inégalités en égalités.

Le problème dépend du paramètre $t$ dans le coût de $x_4$ , ce qui modifie l'optimalité des bases selon les intervalles de $t$ . On procède par analyse paramétrique des coûts réduits ou graphiquement dans l'espace dual. Le dual a deux variables principales associées aux contraintes et se résout en fonction de $t$ . La comparaison primal-dual permet de commenter les changements de base optimaux selon $t$ .

التمرين 2

Exercice 2 — Planarité, formule d'Euler et nombre chromatique

#graph-theory#planar-graphs#euler-formula#chromatic-number#petersen-graph

Démontrer la formule d'Euler : si $G$ est un graphe planaire ayant $n$ sommets, $m$ arêtes et $f$ faces, alors $n-m+f=2$ .
Soit $G$ un graphe planaire connexe à $n \ge 3$ sommets et $m$ arêtes. a) Montrer que $m \le 3n-6$ . b) Si de plus, $G$ ne possède pas de triangle, montrer que $m \le 2n-4$ .
Soit $G$ un graphe planaire d'ordre $n$ et de maille $g$ . a) Montrer que $G$ possède au plus $\frac{g}{g-2}(n-2)$ arêtes. b) En déduire que $K_{3,3}$ et le graphe de Petersen ne sont pas planaires.
Soit $G$ un graphe planaire et notons $\chi(G)$ son nombre chromatique et $\Delta(G)$ son degré maximum. a) Montrer que $\Delta(G) \le 5$ . b) En déduire que $\chi(G) \le 6$ . c) Montrer que si $G$ est un graphe planaire sans triangle, alors $\Delta(G) \le 3$ . d) En déduire que si $G$ est planaire sans triangle, alors $\chi(G) \le 4$ .

◀الحل

Euler : $n-m+f=2$ par récurrence ou suppression d'arêtes hors arbre.

Comme chaque face a au moins 3 arêtes et chaque arête borde 2 faces, $3f \le 2m$ . Avec Euler : $m \le 3n-6$ . Sans triangle, $4f \le 2m$ , donc $m \le 2n-4$ .

Pour la maille $g$ , on a $gf \le 2m$ , d'où $m \le \frac{g}{g-2}(n-2)$ . Cela exclut $K_{3,3}$ et Petersen.

Enfin, tout graphe planaire a un sommet de degré \le 5, donc par récurrence $\chi(G) \le 6$ . Sans triangle, il existe un sommet de degré \le 3 $, donc$ \chi(G) \le 4$.