Maximale snede
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/260px-Max-cut.svg.png)
In de grafentheorie is een maximale snede een snede met maximale grootte of gewicht.
Voor een niet-gerichte graaf met knopenverzameling en kantenverzameling , waarbij aan elke kant een gewicht is toegekend, is een maximale snede een partitie van in twee delen , zodanig dat de som van de gewichten van de kanten tussen en maximaal is.
Het probleem van het vinden van een maximale snede heet in het Engels max-cut problem en is een klassiek probleem uit de grafentheorie. Het is niet enkel theoretisch van belang. Het komt voor bij het ontwerpen van de lay-out van grote geïntegreerde schakelingen en in statistische natuurkunde.[1]
Max-cut-probleem
Het max-cut-probleem, geformuleerd als beslissingsprobleem (voor een gegeven gewicht W, bestaat er een snede met gewicht groter dan of gelijk aan W?) is NP-volledig; het is een van Karps 21 NP-volledige problemen.
Als optimaliseringsprobleem luidt het: vind voor een gegeven graaf een maximale snede. Dit is een NP-moeilijk probleem, zelfs voor niet-gewogen grafen waarvan de kanten geen gewicht hebben (d.w.z. alle kanten hebben gewicht = 1). Dat betekent dat er geen algoritme bestaat dat in polynomiale tijd dit probleem kan oplossen voor een willekeurige graaf.
Het is wel in polynomiale tijd op te lossen voor planaire grafen. Daarvoor kan men aantonen dat het max-cut-probleem kan herleid worden tot het minimum-cost perfect matching-probleem, dat in polynomiale tijd kan opgelost worden voor elke graaf.[2]
Het max-cut-probleem kan geformuleerd worden als een geheeltallig kwadratisch programmeringsprobleem. Benaderende oplossingen worden o.m. gezocht met heuristieken of via relaxatie van het geheeltallige programmeringsprobleem naar een continu optimaliseringsprobleem.
Zie ook
- Max-flow-min-cut-stelling
- ↑ Francisco Barahona, Martin Grötschel, Michael Jünger, Gerhard Reinelt, "An application of combinatorial optimization to statistical physical and circuit layout design." Operational Research (1988), vol. 36, nr. 3, blz. 493–513
- ↑ G.I. Orlova, Ya.G. Dorfman. "Finding the Maximum Cut in a Graph." Engineering Cybernetics (1972), vol. 10, blz. 502-506 (vertaald uit het Russisch). Gearchiveerd op 27 februari 2024.