1. **بیان مسئله:** ما یک شبکه شار داریم با رئوس منبع $s_1$ و $s_2$ که هر کدام می‌توانند حداکثر 7 واحد شار تولید کنند. هدف بررسی سه قسمت است: الف) آیا تابع شار که در آن شار عبوری از همه یال‌ها برابر 1 است، یک تابع شار معتبر است؟ ب) یافتن شار بیشینه در شبکه با توجه به محدودیت‌های تولید شار در رئوس منبع و مقادیر $m=5$ و $d=3$. ج) تعیین برش کمینه در این شبکه. 2. **الف) بررسی تابع شار با شار عبوری 1 در همه یال‌ها:** - تابع شار باید شرایط ظرفیت یال‌ها و قانون جریان در رئوس را رعایت کند. - ظرفیت یال‌ها متفاوت است و برخی کمتر از 1 هستند یا محدودیت تولید شار در منابع وجود دارد. - اگر شار عبوری از همه یال‌ها 1 باشد، باید بررسی کنیم آیا این مقدار از ظرفیت یال‌ها تجاوز نمی‌کند و مجموع شار خروجی از منابع بیش از 7 نیست. - به عنوان مثال، یال $s_1 \to v_1$ ظرفیت 6 دارد، پس عبور 1 واحد مشکلی ندارد. - اما یال $s_1 \to s_2$ با ظرفیت $m=5$ است، عبور 1 واحد مشکلی ندارد. - مجموع شار خروجی از $s_1$ و $s_2$ باید حداکثر 7 باشد، اما اگر همه یال‌ها 1 واحد شار داشته باشند، ممکن است مجموع شار خروجی از منابع بیشتر از 7 شود. - بنابراین، تابع شار با شار عبوری 1 در همه یال‌ها **یک تابع شار معتبر نیست** چون محدودیت تولید شار منابع رعایت نمی‌شود. 3. **ب) یافتن شار بیشینه:** - محدودیت تولید شار در هر منبع: 7 واحد. - ظرفیت یال‌ها: - $s_1 \to v_1 = 6$ - $s_1 \to s_2 = m = 5$ - $s_2 \to v_1 = 4$ - $s_2 \to v_3 = 9$ - $s_2 \to v_4 = 4$ - $v_1 \to v_3 = 12$ - $v_3 \to t = d = 3$ - $v_3 \to v_4 = 7$ - $v_4 \to t = 4$ - شار بیشینه محدود به ظرفیت یال‌های خروجی از منابع و ظرفیت یال‌های مسیر به مقصد است. - شار خروجی از $s_1$ حداکثر $\min(7, 6+5) = 7$ (ظرفیت یال‌ها 6 و 5 است، مجموع 11 ولی محدودیت تولید 7 است). - شار خروجی از $s_2$ حداکثر $7$ (محدودیت تولید). - مسیرهای اصلی به سمت $t$ از طریق $v_3$ و $v_4$ هستند. - ظرفیت $v_3 \to t = 3$ و $v_4 \to t = 4$، مجموع 7. - بنابراین، شار بیشینه کل شبکه برابر با مجموع ظرفیت‌های خروجی از منابع محدود به ظرفیت‌های مسیر به $t$ است. - شار بیشینه $= \min(7+7, 7) = 7$ (ظرفیت مسیر به $t$ محدود کننده است). 4. **ج) برش کمینه:** - برش کمینه مجموعه یال‌هایی است که با حذف آن‌ها، مسیر از منابع به مقصد قطع شود و مجموع ظرفیت آن‌ها حداقل باشد. - برش شامل یال‌های $v_3 \to t$ و $v_4 \to t$ است که مجموع ظرفیت آن‌ها $3 + 4 = 7$ است. - این برش کمینه است چون ظرفیت آن برابر با شار بیشینه است. **پاسخ نهایی:** - الف) خیر، تابع شار با شار عبوری 1 در همه یال‌ها معتبر نیست. - ب) شار بیشینه برابر 7 است. - ج) برش کمینه شامل یال‌های $v_3 \to t$ و $v_4 \to t$ با مجموع ظرفیت 7 است.