Le problème des agents secrets

Soit un groupe d'agents secrets infiltrés dans un pays à surveiller. On construit un graphe où les agents secrets sont les nuds et les arcs représentent un couple d'agents secrets qui se connaissent et peuvent donc se transmettre un message. Le but est d'établir un moyen de passer un message entre tous les agents secrets en minimisant le risque de voir celui-ci passer à l'ennemi. On note $p_{ij}$ la probabilité de voir passer le message à l'ennemi lors de la transmission entre l'agent $i$ et l'agent $j$. On cherche donc à minimiser :

$$1 - \prod_{(i,\,j)\, \in \,T} (1-p_{ij})$$

Cette formule n'étant pas directement utilisable, on doit transformer ce produit en somme. Pour ceci, nous passons au logarithme. Ainsi, maximiser :

$$\prod_{(i,\,j)\, \in \,T} (1-p_{ij})$$

est équivalent à maximiser :

$$\log \left(\prod_{(i,\,j)\, \in \,T} (1-p_{ij}) \right)$$

car la fonction $\log$ est strictement croissante. Finalement, on maximisera :

$$\sum_{(i,\,j)\, \in \,T} \log(1-p_{ij})$$

Le problème se résume donc à rechercher un arbre couvrant de poids maximal après passage au log des poids sur les arcs.