Discussion :

[ericc35]

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

[davcha]

Tu prends le noeud dont la valeur numérique associée est la plus faible. Ca constitue ta 1ère composante connexe.

La 2e composante est constituée de tous les autres noeuds.

Ton problème est mal posé.

[Celelibi]

Tu prends le noeud dont la valeur numérique associée est la plus faible. Ca constitue ta 1ère composante connexe.

La 2e composante est constituée de tous les autres noeuds.

Rien ne garanti que la deuxième composante soit connexe une fois que tu as enlevé la première.

Cela dit, je pense qu'il manque une hypothèse du style : que les deux composantes aient le même nombre de noeuds à +/-1. Mais ça, c'est à ericc35 de nous le dire.

[LinuxUser]

Tu prends le noeud dont la valeur numérique associée est la plus faible. Ca constitue ta 1ère composante connexe.

SI

La 2e composante est constituée de tous les autres noeuds.

est une composante connexe alors OK, sinon tu backtrace et tu prends la deuxième noeud ayant la deuxième plus petite valeur (et ainsi de suite).

[ericc35]

Déjà merci à tous d'avoir répondu.

C'est vrai que les 2 composantes connexes doivent comporter le même nombre de noeuds (j'aurai du l'écrire).

Mes 2 solutions a) et b) fonctionnent mais LENTEMENT (b/ est mieux quand même je crois).

Pour résumer :
a) cherche à maximiser la différence en faisant bouger la frontière
b) cherche à réduire le nombre de composantes connexes

NB je n'ai pas réussi à utiliser dans ce cas très précis les algorithmes de partionnement de graphe dont j'avais parlé dans le premier message (librairie GTL, çà aurait été l'idéal).

Cordialement,
Eric