coupe maximum
Sign in to saveAlso known as Max-Cut problem
a cut of a graph whose size is at least the size of any other cut
Wikidata facts
- Instance of
- computational problem
- Subclass of
- cut
- Image
- Max-cut.svg
Show 2 more facts
- computational complexity
- NP-complete
- opposite of
- minimum cut
Sources (2)
via Wikidata · CC0
Article · Français
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.
Abstract from DBpedia / Wikipedia · CC BY-SA