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

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

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

التمرين 1

Exercice 1 — Graphes connexes et chaînes de longueur maximum

#graph-theory#paths#cycles#connectivity

Soit $G=(V,E)$ un graphe connexe simple.

Montrer que si $P=(v_1,v_2,\dots,v_k)$ est une plus longue chaîne élémentaire dans $G$ , alors tous les voisins de $v_1$ sont dans $P$ .
Montrer que si tous les degrés des sommets de $G$ sont supérieurs ou égaux à deux, alors $G$ possède un cycle élémentaire.
Montrer que si tous les degrés des sommets sont supérieurs ou égaux à $k \geq 2$ , alors $G$ possède un cycle élémentaire de longueur supérieure ou égale à $k+1$ .
Démontrer que deux chaînes de longueur maximum $P$ et $Q$ de $G$ ont au moins un sommet commun. Ont-elles une arête commune ?
En déduire que si $G$ possède deux chaînes de longueur maximum, elles sont obligatoirement de longueur paire. Où se situe le sommet commun ?

◀الحل

1.

Si $v_1$ avait un voisin hors de $P$ , on prolongerait $P$ , contradiction.

2.

Prendre une plus longue chaîne $P$ . Tous les voisins de son extrémité sont dans $P$ , et comme le degré est au moins 2, l'une de ces arêtes crée un cycle.

3.

Même argument : l'extrémité de $P$ a au moins $k$ voisins, tous dans $P$ , ce qui force un cycle de longueur au moins $k+1$ .

4.

Deux chaînes maximales disjointes dans un graphe connexe seraient reliées par une chaîne, permettant d'en construire une plus longue. Donc elles ont un sommet commun. Une arête commune n'est pas nécessaire.

5.

Le sommet commun est un milieu commun, ce qui impose une longueur paire.

التمرين 2

Exercice 2 — Programmation linéaire, dualité et sac à dos

#linear-programming#duality#knapsack#integer-programming

(A) Considérons le problème d'optimisation linéaire

\max Z(x) = 4x_1 - 3x_2

sous contraintes

-x_1 + x_2 \leq 6, \quad x_1 + x_2 = 4, \quad -2x_1 + 4x_2 \geq 2, \quad x_1 \in [-3,2], x_2 \geq 0.

Résoudre ce problème linéaire à l'aide de l'algorithme dual.
Écrire le problème dual.
Trouver les valeurs des variables duales.
Vérifier le théorème des écarts complémentaires.

(B) On considère le problème du sac-à-dos avec objets 1..4, poids 2,3,4,5 et valeurs 3,4,5,6.

Écrire le programme linéaire correspondant.
Décrire une méthode autre que simplex pour le résoudre.

◀الحل

A.

On met le problème en forme standard puis on résout soit graphiquement soit par dualité. Le dual s'écrit avec une variable par contrainte et les bornes sur les variables se traitent via variables d'écart / changement de variables. Les écarts complémentaires permettent de retrouver la solution optimale.

B.

Programme du sac-à-dos :

\max 3x_1 + 4x_2 + 5x_3 + 6x_4

2x_1 + 3x_2 + 4x_3 + 5x_4 \leq C, \quad x_i \in \{0,1\}.

Méthode alternative : programmation dynamique.