حل تشریحی سوال شماره 20 ساختمان داده ها و طراحی الگوریتم ها

گراف جهت دار G با وزن یالهای صحیح و دو رأس خاص s و t از گراف داده شده است. فرض کنید شار بیشینه از s به t در گراف داده شده است. کدام گزینه در خصوص گزاره های زیر درست است؟

(الف) اگر ظرفیت یکی از یالهای G یک واحد افزایش داده شود شار بیشینه در گراف جدید در زمان خطی قابل محاسبه است.

(ب) اگر ظرفیت یکی از یالهای G یک واحد کاهش داده شود شار بیشینه در گراف جدید در زمان خطی قابل محاسبه است.