title: Maximale snede
text: 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.
  
  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.
  
  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
  
  Grafentheorie
  NP-volledig probleem
  NP-moeilijk probleem
  Combinatoriek