📚 الرئيسية
دخول

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

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

⬇️ تحميل☆ حفظ

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

التمرين 1

Exercice 1 — Programme linéaire paramétré et dualité graphique

#linear-programming#duality#parametric-optimization

On considère le PL paramétré

(P(t)){min⁡Z=−3x1+4x2−2x3+tx4x1+x2−x3−x4≤8x1−x2+x3−x4≤4x1,x2,x3,x4≥0,  t≥0.(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, \; t\ge0. \end{cases}
  1. Écrire le problème sous forme standard avec variables d'écart.
  2. Résoudre Q(t)Q(t) en fonction de tt.
  3. Écrire le dual (D(t))(D(t)).
  4. Résoudre (D(t))(D(t)) graphiquement et commenter.
◀الحل

On introduit deux variables d'écart, on résout en fonction de tt par étude des bases possibles, puis on écrit le dual et on confirme graphiquement les solutions.

التمرين 2

Exercice 2 — Planarité, formule d'Euler et coloration

#graph-theory#planar-graphs#euler-formula#graph-coloring
  1. Démontrer la formule d'Euler pour un graphe planaire connexe : n−m+f=2n-m+f=2.
  2. Soit GG planaire connexe à n≥3n\ge3 sommets et mm arêtes. a. Montrer que m≤3n−6m\le3n-6. b. Si GG n'a pas de triangle, montrer que m≤2n−4m\le2n-4.
  3. Si GG a maille gg, montrer qu'il possède au plus gg−2(n−2)\frac{g}{g-2}(n-2) arêtes.
  4. En déduire que K3,3K_{3,3} et le graphe de Petersen ne sont pas planaires.
  5. Si GG est planaire, montrer que Δ(G)≤5\Delta(G)\le5, puis χ(G)≤6\chi(G)\le6, et si GG est planaire sans triangle alors χ(G)≤4\chi(G)\le4.
◀الحل

Preuves classiques par Euler et comptage des incidences face-arête. La borne sur le degré minimum d'un planaire conduit aux résultats de coloration.