Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Coupe maximum
Résumé
En théorie des graphes et en algorithmique, une coupe maximum est une coupe contenant au moins autant d'arêtes que n'importe quelle autre coupe. Une extension de la définition consiste à considérer des poids associés aux arêtes. On considère alors la coupe ayant le poids total maximum.
Les coupes maximums sont des objets utiles notamment en physique théorique et en électronique. Mais elles sont surtout connues pour le problème algorithmique qui consiste à trouver une coupe maximum, appelé couramment MAX-CUT, un problème relativement bien étudié, notamment dans le contexte de l'approximation.
vignette|Une coupe maximum
Étant donné un graphe, et des poids sur les arêtes, une coupe peut-être décrite comme un ensemble de sommets, et le poids de la coupe est alors la somme des poids des arêtes ayant une extrémité à l'intérieur de cet ensemble et l'autre à l'extérieur. Une coupe est maximum si son poids est maximum (parmi toutes les coupes).
Un cas particulier est celui de la coupe de cardinalité maximum, qui correspond à des poids égaux à 1. Dans ce cas le poids d'une coupe est simplement le nombre d'arêtes.
Remarquons qu'a priori il peut y avoir plusieurs coupes maximums, c'est-à-dire plusieurs coupes différentes mais de même cardinal : le cardinal maximum.
On peut aussi considérer l'objet « jumeau » qui est la coupe minimum, et qui a des propriétés complètement différentes, par exemple la relation donnée par le théorème flot-max/coupe-min.
Une généralisation de l'objet est la k-coupe maximum : on considère alors non plus deux composantes mais k composantes.
On considère le problème d'optimisation combinatoire suivant :
Étant donné un graphe G, trouver une coupe maximum.
Et le problème de décision associé :
Étant donné un graphe G et un entier k, existe-t-il une coupe de poids au moins k ?
On considère le plus souvent des poids positifs rationnels.
Le problème peut-être reformulé sous forme d'équations à satisfaire. Cette écriture permet notamment de rapprocher le problème de la conjecture des jeux uniques, en le présentant comme un problème de satisfaction de contraintes.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.