Algorithme de division d'un graphe connexe en deux composants

Question

Supposons que l'on me donne un graphe connexe pondéré. Je voudrais trouver une liste d'arêtes qui peuvent être enlevées du graphique en le laissant divisé en deux composants et que la somme des poids des arêtes enlevées soit petite. Idéalement, j'aimerais avoir la somme minimale, mais je me contenterais d'une approximation raisonnable.

Cela semble être un problème difficile. Y a-t-il de bons algorithmes pour cela? Si cela aide, dans mon cas, le nombre de nœuds est d'environ 50 et le graphique peut être dense, de sorte que la plupart des paires de nœuds auront un bord entre eux.

Answer 1

Je crois que ce que vous cherchez est un algorithme pour calculer la coupe minimale. Le Edmonds-Karp algorithm le fait pour les réseaux de flux (avec les sommets source et collecteur). Hao and Orlin (1994) généraliser ceci aux graphes pondérés dirigés. Leur algorithme fonctionne en O (nm lg (n^2/m)) pour n sommets et m bords. Chekuri et al. (1997) comparer plusieurs algorithmes empiriquement, dont certains ont de meilleurs O grands que Hao et Orlin.

Answer 2

Je pense que vous cherchez un algorithme de coupe minimum. Wikipedia

Avant l'algorithme Edmunds-Karp est venu le Ford-Fulkerson algorithm. Pour ce que ça vaut, le livre Algorithmes [Cormen, Rivest] cite ces deux algorithmes dans le chapitre sur la théorie des graphes.