Il y a un graphe non orienté avec des poids sur les arêtes (les poids sont des entiers non négatifs et leur somme n'est pas grande, la plupart sont 0). J'ai besoin de le diviser en un certain nombre de sous-graphes (disons un graphe de 20 nœuds à 4 sous-graphes de 5 nœuds chacun) d'une manière qui minimise la somme des poids des arêtes entre différents sous-graphes.Existe-t-il un bon algorithme pour ce problème de graphique?
Cela ressemble vaguement au problème de la coupe minimale, mais pas assez proche.
En formulation alternative - il y a un tas de godets, tous les articles appartiennent exactement à deux godets, et je dois partitionner les godets en groupes de godets de manière à minimiser le nombre d'articles dans plusieurs groupes de godets. (les noeuds sont mappés aux seaux, les poids des arêtes sont mappés pour dupliquer le nombre d'éléments)
Eh bien, pour minimiser la somme des arêtes entre les sous-graphes est le même que pour maximiser la somme des arêtes dans les sous-graphes. Quelles sont exactement les contraintes pour scinder le graphe? –
Est-ce un problème de segmentation d'image? – Jacob
Voulez-vous vraiment dire «bon» ou voulez-vous dire «optimal»? Je peux penser à quelques "bonnes" approches :) – dvogel