Maximale snede

Maximale snede doorheen deze graaf. De grootte van de snede is 5.

In de grafentheorie is een maximale snede een snede met maximale grootte of gewicht.

Voor een niet-gerichte graaf $G=(V,E)$ met knopenverzameling $V$ en kantenverzameling $E$, waarbij aan elke kant $(i,j)\in E$ een gewicht $w_{ij}$ is toegekend, is een maximale snede een partitie van $V$ in twee delen $S,T$, zodanig dat de som van de gewichten van de kanten tussen $S$ en $T$ 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.

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 $G$ 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.

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

Bronnen, noten en/of referenties