برش (نظریه گراف)
در نظریه گراف، یک برش یک افراز از رأسهای یک گراف در دو مجموعه مجزا میباشد. هر برش یک مجموعه-برش ایجاد میکند که مجموعه یالهایی است که هر راس آنها در یک افراز قرار دارد. در یک شبکه شاره یک برش s-t یک برش است که در آن source و sink باید در مجموعههای مجزا باشند و مجموعه-برش آن از یالهایی تشکیل شدهاست که از source به سمت sink میروند. ظرفیت یک برش s-t برابر مجموع ظرفیت یالها در مجموعه-برش است.[۱]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Graph-schnitt.png/220px-Graph-schnitt.png)
جستارهای وابسته
ویرایشمنابع
ویرایش- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), مقدمهای بر الگوریتمها (2nd ed.), MIT Press and McGraw-Hill, p. 563,655,1043, ISBN 0-262-03293-7.
- مشارکتکنندگان ویکیپدیا. «Cut (graph theory)». در دانشنامهٔ ویکیپدیای انگلیسی، بازبینیشده در ۲ ژوئیه ۲۰۱۷.
پیوند به بیرون
ویرایشدر ویکیانبار پروندههایی دربارهٔ برش (نظریه گراف) موجود است.