Trouver la coupe minimale d'un graphique non orienté

25

Voici une question d'un examen passé que j'essaie de résoudre:

Pour un graphique non orienté avec des poids positifs , j'essaie de trouver la coupe minimale. Je ne connais pas d'autres façons de faire cela en dehors de l'utilisation du théorème de coupure max-débit min. Mais le graphique n'est pas orienté, alors comment dois-je le diriger? J'ai pensé à diriger les bords aux deux extrémités, mais alors quel sommet serait la source et quel sommet serait le puits? Ou existe-t-il un autre moyen de trouver la coupe minimale?Gw(e)≥0

algorithms graph-theory Jozef
la source
1
Si vous n'avez pas de source et de cible dans le graphique d'origine, je suppose que vous devrez essayer plusieurs choix. (Pour tout s et t , la coupe minimale peut ne pas séparer les deux.)
Raphael
Essayez-vous de trouver la coupe minimale pour les nœuds source et récepteur donnés ou la coupe minimale du graphique?
Peter
@Peter: La coupe minimale du graphique.
Jozef

Réponses:

13

Il existe de nombreux algorithmes pour trouver la coupe minimale d'un graphe non orienté. L'algorithme de Karger est un algorithme randomisé simple mais efficace.

En bref, l'algorithme fonctionne en sélectionnant les bords uniformément au hasard et en les contractant avec des boucles auto supprimées. Le processus s'arrête lorsqu'il reste deux nœuds et que les deux nœuds représentent une coupure. Pour augmenter la probabilité de réussite, l'algorithme randomisé est exécuté plusieurs fois. En faisant les descentes, on garde la trace de la plus petite coupe trouvée jusqu'à présent.

Voir l'entrée Wikipedia pour plus de détails. Pour peut-être une meilleure introduction, consultez le premier chapitre de Probability and Computing: Randomized Algorithms and Probabilistic Analysis de Michael Mitzenmacher et Eli Upfal.

Juho
la source
Est-ce un algorithme d'approximation?
Strin
@Strin C'est un algorithme randomisé qui trouve la coupure minimale avec une forte probabilité.
Juho
1
Je ne pense pas que Karger est approprié pour trouver une coupe de poids minimum. La dérivation de la probabilité qu'il trouve une coupe minimale dépend de la recherche d'une coupe de cardinalité minimale; Il est très peu probable que Karger trouve une coupe minimale avec de nombreux bords légers.
Sumudu Fernando
8

Pour chaque bord non dirigé créez deux bords dirigés ( u , v , w e i g h t ) et ( v , u , w e i g h t ) .(u,v,weight)(u,v,weight)(v,u,weight)

... mais alors quel sommet serait la source et quel sommet serait le puits?

Peu importe.

Pratik Deoghare
la source
1
Pourquoi ça n'a pas d'importance?
The Coding Wombat
1

L' algorithme Ford-Fulkerson devrait fonctionner pour vous. Vous pouvez créer deux faux sommets, à savoir. la source et le puits.

Jetez également un œil à l' algorithme Edmonds-Karp . Il en existe deux variantes:

  1. Une version choisit le chemin le plus court
  2. Autre choisit un chemin avec la capacité maximale

, par opposition à Ford-Fulkerson qui choisit une voie arbitraire.

Ceci est une bonne ressource.

ajmartin
la source
Bienvenue sur cs.stackexchange! Cela pourrait aider l'OP si vous pouviez expliquer davantage comment les faux sommets sont connectés au graphique existant. Et quels seront les poids des bords des nouveaux bords.
Paresh