Algorithme de Karger

En algorithmique des graphes, l'algorithme de Karger est un algorithme probabiliste pour le problème de la coupe minimum (MIN-CUT). C'est donc un algorithme utilisant une source d'aléas, pour produire une solution correcte avec une bonne probabilité. Le problème en question est le suivant : étant donné un graphe non orienté trouver un ensemble de sommets non trivial minimisant le nombre d'arêtes sortant de cet ensemble. L'outil principal de l'algorithme est la contraction aléatoire d'arêtes, qui fait décroître le nombre de sommets. Il est dû à David Karger et a été publié en 1993. Plusieurs variations ont ensuite été proposées. Coupe minimum L'objet du problème est un graphe non orienté, un objet mathématique qui permet par exemple de représenter des réseaux de communications. Les nœuds du réseau sont appelés les sommets et les connexions sont les arêtes. Mathématiquement, un graphe non orienté G est la donnée d'un ensemble fini, noté V (les sommets) et d'un sous-ensemble E de V×V (les arêtes). On parle de coupe pour désigner deux concepts proches : une partition des sommets en deux sous-ensembles non vides ou bien les arêtes ayant une extrémité dans chacun de ces sous-ensembles. Lorsqu'on parle du cardinal d'une coupe on entend le nombre d'arêtes de cette coupe. Une coupe minimum dans un graphe non orienté est une coupe de cardinal minimum. Il peut exister plusieurs coupes minimums. Le concept de coupe minimum est relié à un autre concept fondamental en théorie des graphes, la notion de flot maximum. En effet le théorème flot-max/coupe-min établit qu'étant donné deux sommets particuliers s et t dans le graphe, le flot maximum pouvant passer par le réseau de s à t est égal au cardinal de la coupe minimum avec la contrainte que s doit être dans un sous-ensemble et t dans l'autre. Le problème de la coupe minimum consiste, étant donné un graphe, à déterminer une coupe minimum. Ce problème peut être résolu de façon déterministe en cherchant un flot maximum entre toute paire de sommets grâce au théorème flot-max/coupe-min.