Graphes probabilistes
matT_1309_04_06C
Ens. de spécialité
38
CORRIGE
Antilles, Guyane • Septembre 2013
Exercice 2 • 5 points
Une entreprise de produits cosmétiques fait réaliser une étude marketing sur une population donnée.
Cette étude montre que, lors de la sortie d'une nouvelle crème hydratante, la probabilité qu'une cliente l'achète lors de la première vente promotionnelle est de 0,2.
De plus, lorsqu'une cliente a acheté une crème hydratante lors d'une vente promotionnelle, la probabilité qu'elle en achète à nouveau lors de la vente promotionnelle suivante est de 0,8. Lorsqu'une cliente n'a pas acheté de crème hydratante, la probabilité pour qu'elle en achète à la vente promotionnelle suivante est de 0,3.
étant un entier naturel non nul, on note :
la probabilité qu'une cliente achète une crème hydratante lors de la
‑ième vente promotionnelle.
la probabilité qu'une cliente n'achète pas une crème hydratante lors de la 
-ième vente promotionnelle.
la matrice ligne traduisant l'état probabiliste à la 
-ième vente promotionnelle.
. (0,5 point)
quand il y a achat 
quand il n'y a pas achat. (0,75 point)
de transition associée à ce graphe. (0,5 point)
et 
. D'après ces résultats, quel est l'effet de ces trois premières ventes promotionnelles ? (1 point)
pour cette situation. Le déterminer. (1 point)
L'entreprise souhaite répartir les produits dans des lots constitués de produits ne présentant aucune incompatibilité d'achat. Combien de lots doit-elle prévoir au minimum ? Justifier votre réponse à l'aide d'un algorithme et proposer une répartition des produits. (1,25 point)
Les thèmes en jeu
Graphe probabiliste • Matrice.
Les conseils du correcteur
> 1. a) Déterminer un état probabiliste
D'après l'énoncé, la probabilité qu'une cliente achète la crème lors de la première vente promotionnelle est 0,2, donc 
.
On en déduit 
, d'où :
b) Représenter une situation par un graphe probabiliste
> 2. a) Écrire la matrice de transition d'un graphe probabiliste
Par définition, la matrice de transition d'un graphe probabiliste est la matrice M telle que, pour tout entier naturel 
:
.
D'après l'énoncé :
Donc la matrice de transition du graphe précédent est :
b) Déterminer deux états probabilistes
.
.
> 3. Déterminer un état stable
Un état stable 
est défini par 
, soit :
, qui équivaut à 
, c'est-à-dire :
.
De plus 
, donc le couple 
est solution du système :
D'où 
.
> 4. Étudier à l'aide d'un graphe la répartition de produits dans des lots proposés à la vente
Le problème peut être considéré comme un problème de coloration du graphe : chaque couleur représente un lot de produits, on cherche le nombre minimal de couleurs à utiliser pour colorier les sommets, deux sommets adjacents ne devant pas être de la même couleur.
Pour cela :
Notez bien
Le degré d'un sommet d'un graphe est le nombre d'arêtes dont ce sommet est une extrémité.
- on détermine le degré de chaque sommet
- dans un tableau, on range les sommets par ordre de degré décroissant
- on colorie les sommets par des couleurs notées 1, 2, 3… en attribuant successivement à chaque sommet la plus « petite » couleur (celle de plus petit numéro) qui n'est pas déjà portée par un sommet adjacent.
D'où le tableau suivant :
| Sommet | E | G | A | F | H | B | C | D |
| Degré | 6 | 6 | 5 | 4 | 4 | 3 | 2 | 2 |
| Couleur | 1 | 2 | 3 | 4 | 5 | 1 | 3 | 2 |
- On attribue au sommet E la couleur 1
- G est adjacent à E, on lui attribue la couleur 2
- A est adjacent à E et G, on lui attribue la couleur 3
- F est adjacent à E, G et A, on lui attribue la couleur 4
- H est adjacent à E, G, A et F, on lui attribue la couleur 5
- B n'est pas adjacent à E, on lui attribue la couleur 1
- C n'est pas adjacent à A, on lui attribue la couleur 3 (C est adjacent à E et G, on ne peut pas lui attribuer les couleurs 1 et 2)
- D est adjacent seulement à B et E, qui ont la couleur 1 D peut prendre la couleur 2.
Une répartition en 5 lots, correspondant aux 5 couleurs utilisées est par exemple :
{E B} {G D} {A C} {F} {H}