مسابقة دكتوراه 2017 — جامعة بجاية — الموضوع 02

Soient $G = (V, E)$ un graphe non orienté simple (sans boucles), et $c$ une fonction (représentant par exemple un coût) sur l'ensemble des arêtes $E$, avec $|V| = n$ et $|E| = m$.

Considérons le problème de recherche d'une chaîne Hamiltonienne (tournée) de coût minimum sur $G$. Le problème est appelé le problème du voyageur de commerce symétrique (STSP).

1. Donner la formulation du problème décrit ci-dessus en un problème linéaire en nombres entiers (justifier chaque étape de la formulation).

2. Soit $v_1$ un sommet de $V$. On appelle 1-arbre de $G$ noté $A$, un graphe partiel qui est un arbre sur les $n-1$ sommets $V \setminus \{v_1\}$, plus deux arêtes reliant le sommet $v_1$ à $V \setminus \{v_1\}$.

Montrer que le problème de recherche du 1-arbre de poids minimum est une relaxation du problème (STSP), puis le formuler en un problème linéaire en nombres entiers.

3. Montrer que pour $n \ge 4$, si la solution du problème relaxé n'est pas une tournée (un 1-arbre $A$), alors il existe un sommet dans $A$ de degré supérieur ou égal à 3.

4. À l'aide de la méthode branch and bound (basée sur la relaxation décrite) résoudre le problème (STSP) défini par la matrice suivante des coûts :

$$\begin{pmatrix} - & 3 & 10 & 5 \\ - & - & 9 & 2 \\ - & - & - & 1 \\ - & - & - & - \end{pmatrix}$$

I. Supposons que le temps qu'il fait d'une journée à la suivante est décrit par une chaîne de Markov sur les états $0, 1, 2$ ($0$ pour ensoleillé, $1$ pour nuageux, $2$ pour pluvieux) dont la matrice de transition est donnée par :

$$P = \begin{pmatrix} 1/2 & 1/2 & 0 \\ 1/4 & 1/2 & 1/4 \\ 0 & 1/2 & 1/2 \end{pmatrix}.$$

On est jeudi et c'est nuageux. Déterminer :

(a) la probabilité que les trois prochains jours soient ensoleillés ;

(b) la probabilité que dimanche prochain soit ensoleillé.

II. Une chaîne de Markov sur trois états, disons $0$, $1$ et $2$, a comme matrice de transition :

$$P = \begin{pmatrix} 1/4 & 3/4 & 0 \\ 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \end{pmatrix}.$$

(a) Déterminer les classes d'états et leur type ;

(b) Diagonaliser la matrice de transition $P$ ;

(c) Calculer la matrice de transition en $n$ pas ;

(d) Déduire la distribution stationnaire de cette chaîne.