Commune · Savoirs
Coupe maximum
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.
1 exemplaire en circulation
Sur Wikipédia
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.
Texte : Wikipédia, CC BY-SA 4.0. · Image : Miym (CC BY-SA 3.0) ·
Cartes voisines
-
★
Problème de flot maximum
-
T★
Théorème flot-max/coupe-min
Théorème de la théorie des graphes
-
★
Problème de la clique
-
★★
Degré (théorie des graphes)
Théorie des graphes
-
★★
Maximum subarray problem
The task of finding a contiguous subarray with the largest sum in a given array of numbers
-
T★★
Théorème de Turán