Olarak grafik teorisi , bir kesik , bir grafik, iki alt-grup halinde köşelerin bir bölümdür. Ayrıca , bölümün her bir alt kümesinde bir sona sahip olan kenar kümesini kes olarak adlandırıyoruz .
Kenarların bir ağırlığı varsa, kesme ağırlığı, kesilen kenarların ilgili ağırlıklarının toplamıdır. Aksi takdirde bölümdeki kenar sayısıdır.
Bu nesne, ağlarla ilgili birçok sorunun modellenmesinde ortaya çıkar, burada bir kesik st , yani belirtilen iki köşeyi s ve t ayıran bir kesim arıyoruz .
Doğal problemler, minimum ağırlık st fit ve maksimum ağırlık st fit bulmaktır .
Minimum kesme sorunu (MIN-KESME) eşdeğerdir maksimum akış sorununa göre, akış-maks / kesme dakika teoremi . Polinom zamanda çözülebilir .
Maksimum kesme problemi (MAKS-KES) 'dir NP-tam (o biridir Karp 21 NP-tam problemlerin ).
Diğer bir klasik sorun, daha az yoğun kesimdir (en seyrek kesim ). Bir kesimin yoğunluğunu, kesimdeki kenar sayısının kesimin iki parçasından küçük olan düğüm sayısına oranı olarak tanımlarız. Sorun, daha küçük yoğunlukta bir kesim bulmaktır.