Discussion :

[arnobidul]

je suis en train de developper une application de gestion de compte mais je bute sur la simplification du graphe qui représente ces comptes...

ex : X doit 30 euros à Y et Z doit 10 euros à X
la simplification serait : X doit 20 à Y et Z doit 10 à Y, ca fé 10 euros en moins a manipuler...

le graphe est représenté par un vecteur de sommet et un vecteur d'arc...

si vous avez une tite idée, merci

[FrancisSourd]

Si j'ai bien compris, il s'agit de trouver un graphe équivalent au graphe de départ pour lequel la somme des valeurs sur les arcs est minimale. On dit que deux graphes sont équivalents si pour tous les noeuds, la somme des valeurs entrantes moins la somme des valeurs sortantes sont identiques.

Une première idée serait de regarder du côté des algorithmes de flots.

Une deuxième idée serait de regarder si le graphe contient un chemin de plus de deux arcs. Si c'est le cas, on suppose que l'arc est entre un noeud a et un noeud b. On appelle v la plus petite valeur rencontrée sur le chemin. On retranche v de tous les arcs du chemin et on rajoute à l'arc (a,b) la valeur v (si cet arc n'existe pas, on le crée avec la valeur v).
Cette transformation fait baisser le coût total (au sens défini au début).
On itère la procédure jusqu'à ce qu'il n'y ait plus de chemin de longueur 2. On obtient a priori un minimum local mais c'est bien possible que cela soit l'optimum. On sait en tout cas que l'optimum est un graphe biparti, tous ceux qui un solde positif d'un côté et tous ceux qui sont négatifs de l'autre.

[FrancisSourd]

Je reviens sur la première idée. Il s'agit bien d'un problème de transport (c'est un cas particulier des problèmes de flots).
On met à gauche ceux qui ont un solde négatif et à droite ceux qui ont un solde positif. On sait qu'il y a une solution qui correspond à un graphe biparti.

On peut construire une solution simplement:
on prend le premier de la liste des "négatifs" (il doit n1) et on lui fait donner au premier positif (qui doit recevoir p1). On fixe la transaction à v=min(p1,n1). et on remplace n1 par n1-v et p1 par p1-v. On itère celà tant que tout le monde n'est pas à 0. On obtient ainsi un graphe sans redondance, qui n'a évidemment rien à voir avec le graphe initial mais qui est équivalent.

[phlip]

Francis, je crois que la seconde solution de ta première réponse était la bonne piste.

Les chemins de longueur 2 sont faciles à suivre puisque qu'ils comprennent tous un noeud dont le degré en entrée et le degré en sortie sont tous deux strictement positifs.

L'algorithme est alors:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
-1-     établir la liste des noeuds de degrés en entrée et en sortie > 0.
-2-     pour chacun de ces noeuds, B:
-2a-      tant qu'il existe un chemin A -> B -> C
-2a1-       ajouter un arc A -> C de poids égal au min des poids de A->B et de
B->C
             (ou ajouter le min au poids de l'arc A->C existant).
-2a2-       si C->A a un poids non nul
-2a2a-        si le poids de C->A est plus petit que celui de A->C
-2a2a1-         soustraire le poids de C->A au poids de A->C
-2a2a2-         supprimer l'arc C->A
-2a2b-        si le poids de C->A est plus grand que celui de A->C
-2a2b1-         soustraire le poids de A->C au poids de C->A
-2a2b2-         supprimer l'arc A->C
-2a2c-        si le poids de C->A est égal à celui de A->C
-2a2c1-         supprimer l'arc C->A
-2a2c2-         supprimer l'arc A->C
-2a3-       diminuer les poids A->B et B->C de ce min.
-2a4-       si A->B a un poids nul, supprimer cet arc.
-2a5-       si B->C a un poids nul, le supprimer également.
-2b-      supprimer B de la liste.

lorsque la liste est vide, on a une solution.

l'algorithme me semble correct car:
- il est possible de supprimer le noeud B de la liste au -2b- car si au moins un des degrés de B, en entrée ou en sortie, n'est pas nul, alors il existe encore un chemin A->B->C à traiter.
- Il est impossible d'ajouter un noeud sur la liste au cours du traitement car les degrés en entrée et en sortie des noeuds du graphe initial peuvent s'annuler, mais ne peuvent passer de nul à non nul.
- lorsque l'on supprime des arcs parmi A->B, B->C, A->C ou C->A, on peut éventuellement invalider la présence de A ou de C sur la liste, mais ce n'est pas un problème car lorsque ce noeud est traité, on ne trouve pas de chemin A->B->C et on passe directement de -2- à -2b-.
- la solution obtenue doit bien être un minimun global car le graphe peut constamment être vu comme une circulation dont les demandes aux noeuds restent constantes, avec des capacités de flux maximales infinies. Si on attribue à chaque arc un même coût (par exple 1), notre problème revient à trouver la circulation de coût minimum. Or on sait que l'algorithme du simplexe résout ce problème en supprimant tout cycle de coût négatif dans le graphe des écarts de la circulation, et il se trouve que l'algorithme exposé supprime justement tous ces cycles, donc que la solution est optimale.

L'avantage de cet algorithme est que le graphe final correspond à l'esprit de 'transfert de dette' qui était dans l'énoncé, c'est à dire qu'il est une version simplifiée mais dans laquelle on retrouve les relations du graphe initial.