Exercice 2 - Minimiser le nombre de transactions

$m$ personnes partent en vacances et paient de façon anarchique pendant leur séjour. A leur retour, ils font les comptes et le chargé des comptes dessine un graphe orienté $G = (S, A)$ muni d'une valuation $c$ où

• chaque élément de $S$ est une personne
• chaque couple $(i, j) \in A$ signifie la personne $i$ doit $c(i, j)$ euros à la personne $j$

Représentez le graphe correspondant aux donnés suivantes :

1. $A$ doit 147 euros à $C$
2. $B$ doit 57 euros à $A$
3. $E$ doit 228 euros à $B$
4. $B$ doit 129 euros à $D$
5. $D$ doit 78 euros à $A$
6. $C$ doit 45 euros à $B$
7. $B$ soit 187 euros à $E$

On remarque que ce graphe contient des circuits, et que pour certains couples, de sommets, il existe plusieurs chemins. Utiliser le graphe tel qu'il est pour planifier les remboursements conduirait à des remboursements redondants ($C$ donne à $B$ qui donne à $A$ qui donne à $C$...). En réfléchissant, il remarque que peu importe qui rembourse qui, ce qui compte, c'est que chacun retrouve son argent. Pour simplifier le problème, il décompose donc $S$ en deux sous-ensembles $S^+$ (ceux à qui on doit de l'argent qu'ils n'en doive) et $S^-$ (ceux qui doivent de l'argent plus qu'on leur en doit). Chaque sommet $s$ est étiqueté par la valeur

$$\vert\sum_{t \in \Gamma^+(s)} c(s, t) - \sum_{t \in \Gamma^-(s)} c(t, s)\vert$$

Quels sont les sommets et les étiquettes des sommets de ce nouveau graphe ? La question est de trouver comment placer les arêtes de la façon la plus simple possible. Modélisez ce problème comme un problème de flot max. Nous souhaitons maintenant minimiser le nombre de transaction. Est-ce possible avec un algorithme de flot maximum ? Nous verrons dans une autre section que ce problème est NP-Complet.