سوال ۷۸ کنکور ارشد علوم کامپیوتر ۱۴۰۲

مقدار برش کمینه (min cut) میان $s$ و $t$ در گراف زیر، کدام است؟

شبکه‌ی جهت‌دار دارای مبدأ $s$، دو رأس میانی چپ $a$ (بالا) و $b$ (پایین)، دو رأس میانی راست $c$ (بالا) و $d$ (پایین)، و مقصد $t$ است، با ظرفیت یال‌ها: $s\to a = ۵,\quad s\to b = ۷,\quad a\to c = ۱,\quad a\to d = ۵,\quad b\to c = ۴,\quad b\to d = ۴,\quad c\to t = ۸,\quad d\to t = ۵.$