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

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

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

⬇️ تحميل☆ حفظ

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

التمرين 1

Exercice 1 — Forme standard, dualité et résolution paramétrique

#linear-programming#duality#standard-form#graphical-solution

On considère le programme linéaire

(P(t))  min⁡Z=−3x1+4x2−2x3+tx4(P(t)) \; \min Z = -3x_1 + 4x_2 - 2x_3 + t x_4

sous contraintes

x1+x2−x3−x4≤8,x1−x2+x3−x4≤4,x1,x2,x3,x4≥0,x_1 + x_2 - x_3 - x_4 \leq 8, \quad x_1 - x_2 + x_3 - x_4 \leq 4, \quad x_1,x_2,x_3,x_4 \geq 0,

avec t≥0t \geq 0.

  1. Écrire le problème sous forme standard en ajoutant deux variables d'écart x5,x6x_5, x_6.
  2. Résoudre (Q(t))(Q(t)) en fonction de tt.
  3. Écrire le problème dual (D(t))(D(t)) de (Q(t))(Q(t)).
  4. Résoudre (D(t))(D(t)) graphiquement. Commenter.
◀الحل

On ajoute x5,x6≥0x_5, x_6 \geq 0 pour transformer les inégalités en égalités. Le problème dual s'écrit avec deux variables duales correspondant aux deux contraintes. La résolution paramétrique en fonction de tt s'obtient par étude des sommets admissibles et comparaison des valeurs objectives. Le commentaire porte sur la cohérence primal-dual et la dualité forte.

Reˊsolution par analyse des bases optimales selon t\boxed{\text{Résolution par analyse des bases optimales selon } t}

التمرين 2

Exercice 2 — Formule d'Euler et graphes planaires sans triangles

#graph-theory#planar-graphs#euler-formula#chromatic-number#petersen-graph
  1. Démontrer la formule d'Euler : si GG est un graphe planaire ayant nn sommets, mm arêtes et ff faces, alors n−m+f=2n-m+f=2.
  2. Soit GG un graphe planaire connexe ayant nn sommets (n≥3n \geq 3) et mm arêtes. a) Montrer m≤3n−6m \leq 3n-6. b) Si, de plus, GG ne possède pas de triangle, montrer que m≤2n−4m \leq 2n-4.
  3. Soit GG un graphe planaire d'ordre nn et de maille gg. a) Montrer que GG possède au plus gg−2(n−2)\frac{g}{g-2}(n-2) arêtes. b) En déduire que K3,3K_{3,3} et le graphe de Petersen ne sont pas planaires.
  4. Soit GG un graphe planaire et notons χ(G)\chi(G) son nombre chromatique et Δ(G)\Delta(G) son degré maximum. a) Montrer que Δ(G)≤5\Delta(G) \leq 5. b) En déduire que χ(G)≤6\chi(G) \leq 6. c) Montrer que si GG est planaire et sans triangle, alors Δ(G)≤3\Delta(G) \leq 3. d) En déduire que si GG est planaire et sans triangle, alors χ(G)≤4\chi(G) \leq 4.
◀الحل

Résultats classiques sur les graphes planaires. La formule d'Euler donne les bornes d'arêtes. Sans triangles, chaque face a au moins 4 arêtes. Les non-planarités de K3,3K_{3,3} et du graphe de Petersen se déduisent de ces bornes. La borne sur χ(G)\chi(G) suit de la coloration gloutonne et du fait qu'un graphe planaire possède un sommet de petit degré.

χ(G)≤6,χ(G)≤4 si G est planaire sans triangle\boxed{\chi(G) \leq 6, \quad \chi(G) \leq 4 \text{ si } G \text{ est planaire sans triangle}}