In graafiteoria , joka on leikkaus , joka kuvio on osio pisteiden kahteen osajoukkoja. Kutsumme myös leikkausjoukkoa reunoja, joilla on loppu osion kussakin osajoukossa.
Jos reunoilla on paino, leikattu paino on leikattujen reunojen vastaavien painojen summa. Muuten se on osan reunojen lukumäärä.
Tämä esine esiintyy monien verkoihin liittyvien ongelmien mallinnuksessa, jossa etsimme leikattua st: tä , toisin sanoen leikkausta, joka erottaa kaksi määritettyä kärkeä s ja t .
Luonnollinen ongelmat löytävät vähimmäispaino s istuvuus ja enimmäispaino st sovi.
Vähintään leikkaus ongelma (MIN-CUT) vastaa suurin virtauksen ongelma , mukaan virtaus-max / cut-min lause . Se voidaan ratkaista polynomissa .
Suurin leikkaus ongelma (MAX-CUT) on NP-täydellinen (se on yksi ja Karp n 21 NP-täydelliset ongelmat ).
Toinen klassinen ongelma on vähemmän tiheä leikkaus ( harvoin leikattu ). Määritämme leikkauksen tiheyden leikkauksen reunojen lukumäärän ja leikkauksen kahdesta osasta pienemmän solmujen lukumäärän suhteeksi. Ongelmana on löytää pienemmän tiheyden leikkaus.