Bonjour,

Soit un graphe (connexe) avec une valeur numérique associée a chaque noeud.
Je veux séparer ce graphe en 2 composantes connexes (chaque composante aura pour valeur la somme des valeurs des noeuds la composant), telle que la différence entre les 2 valeurs des 2 composantes soit MAXIMALE.

J'ai essaye plusieurs choses :
----------------------------
1) utiliser des algorithmes de découpage de graphe (ratio_cut_partition et FM), mais ils cherchent
plutôt a séparer en 2 régions equilibrées (et encore avec plusieurs composantes connexes).

2) C++ direct en partant :
a) soit d'une frontière initiale et en affinant progressivement.
Il y donc 2 composantes connexes au départ (la différence est a maximiser).
PERFS : BOF !!!

b) soit en affectant tous les départements dont le numéro est élevé (supérieur a la
médiane) a la région FORTE, et les autres a la région FAIBLE.
Il y donc plus de 2 composantes connexes au départ (la différence est par contre
MAXIMALE)
PERFS : ca a l'air mieux qu'en a) mais BOF !!!

Voila si vous avez des idées, je suis preneur.

Cordialement,
Eric