برش (نظریه گراف)

در نظریه گراف، یک برش یک افراز از رأس‌های یک گراف در دو مجموعه مجزا می‌باشد. هر برش یک مجموعه-برش ایجاد می‌کند که مجموعه یال‌هایی است که هر راس آن‌ها در یک افراز قرار دارد.
در یک شبکه شاره یک برش s-t یک برش است که در آن source و sink باید در مجموعه‌های مجزا باشند و مجموعه-برش آن از یال‌هایی تشکیل شده‌است که از source به سمت sink می‌روند. ظرفیت یک برش s-t برابر مجموع ظرفیت یال‌ها در مجموعه-برش است.

جستارهای وابسته 
 همبندی
 برش کمینه
 برش بیشینه

منابع

پیوند به بیرون 

بهینه‌سازی ترکیبیاتی
همبندی گراف