maximale snede

In de grafentheorie is een maximale snede een 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.