V teorii grafů je výřez grafu rozdělením vrcholů do dvou podmnožin. Říkáme také ořezat sadu hran s koncem v každé podmnožině oddílu.
Pokud mají hrany váhu, je hmotnost řezu součtem příslušných hmotností řezaných hran. Jinak je to počet hran v řezu.
Tento objekt se objevuje v modelování mnoha problémů týkajících se sítí, kde hledáme řez st , tj. Řez oddělující dva určené vrcholy s a t .
Přirozené problémy spočívají v nalezení minimální hmotnosti st fit a maximální hmotnosti st fit.
Problém minimálního řezu (MIN-CUT) je ekvivalentní problému maximálního průtoku podle věty o průtoku max / řez-min . Lze to vyřešit v polynomiálním čase .
Problém maximálního řezu (MAX-CUT) je NP-úplný (je to jeden z 21 problémů Karpových NP-úplných ).
Dalším klasickým problémem je méně hustý řez ( nejspasnější řez ). Hustotu řezu definujeme jako poměr počtu hran v řezu k počtu uzlů v menší ze dvou částí řezu. Problém je najít řez menší hustoty.