شار با تقاضا¶
در یک شبکه شار معمولی، شار یک یال فقط از بالا توسط ظرفیت $c(e)$ و از پایین توسط 0 محدود می‌شود. در این مقاله، شبکه‌های شاری را بررسی می‌کنیم که در آن‌ها، علاوه بر محدودیت ظرفیت، شار هر یال باید از یک حد پایین نیز تبعیت کند. این حد پایین را با یک تابع تقاضا (demand) به نام $d(e)$ مشخص می‌کنیم:
بنابراین، هر یال یک مقدار شار حداقلی دارد که باید از آن عبور داده شود.
این مسئله، تعمیمی از مسئله شار معمولی است، زیرا با قرار دادن $d(e) = 0$ برای تمام یال‌های $e$، به یک شبکه شار معمولی می‌رسیم. توجه داشته باشید که در شبکه شار معمولی، پیدا کردن یک شار معتبر بسیار پیش‌پاافتاده است؛ قرار دادن $f(e) = 0$ برای همه یال‌ها خود یک شار معتبر است. اما اگر شار هر یال ملزم به برآورده کردن یک تقاضا باشد، آنگاه پیدا کردن یک شار معتبر به خودی خود به یک مسئله نسبتاً پیچیده تبدیل می‌شود.
دو مسئله را در نظر خواهیم گرفت:
- پیدا کردن یک شار دلخواه که تمام محدودیت‌ها را برآورده کند
- پیدا کردن شار کمینه که تمام محدودیت‌ها را برآورده کند
پیدا کردن یک شار دلخواه¶
تغییرات زیر را در شبکه ایجاد می‌کنیم. یک منبع جدید $s'$ و یک چاه جدید $t'$ اضافه می‌کنیم. همچنین، یک یال جدید از منبع $s'$ به هر رأس دیگر، یک یال جدید از هر رأس به چاه $t'$ و یک یال از $t$ به $s$ اضافه می‌کنیم. علاوه بر این، تابع ظرفیت جدید $c'$ را به صورت زیر تعریف می‌کنیم:
- $c'((s', v)) = \sum_{u \in V} d((u, v))$ برای هر یال $(s', v)$.
- $c'((v, t')) = \sum_{w \in V} d((v, w))$ برای هر یال $(v, t')$.
- $c'((u, v)) = c((u, v)) - d((u, v))$ برای هر یال $(u, v)$ در شبکه قدیمی.
- $c'((t, s)) = \infty$
اگر شبکه جدید یک شار اشباع‌کننده داشته باشد (شاری که در آن تمام یال‌های خروجی از $s'$ کاملاً پر شده باشند، که معادل این است که تمام یال‌های ورودی به $t'$ نیز کاملاً پر شده باشند)، آنگاه شبکه با تقاضا، یک شار معتبر دارد و شار واقعی را می‌توان به راحتی از روی شبکه جدید بازسازی کرد. در غیر این صورت، شاری که تمام شرایط را برآورده کند وجود ندارد. از آنجایی که یک شار اشباع‌کننده لزوماً یک شار بیشینه است، می‌توان آن را با هر الگوریتم شار بیشینه، مانند الگوریتم Edmonds-Karp یا الگوریتم Push-relabel، پیدا کرد.
درک صحت این تبدیل‌ها دشوارتر است. می‌توانیم موضوع را این‌گونه تصور کنیم: هر یال $e = (u, v)$ با $d(e) > 0$ در اصل با دو یال جایگزین می‌شود: یکی با ظرفیت $d(e)$ و دیگری با ظرفیت $c(e) - d(e)$. هدف ما یافتن شاری است که یال اول را اشباع کند (یعنی شار عبوری از این یال باید برابر با ظرفیت آن باشد). یال دوم اهمیت کمتری دارد؛ شار عبوری از آن می‌تواند هر مقداری باشد، به شرطی که از ظرفیتش بیشتر نشود. هر یالی را که باید اشباع شود در نظر بگیرید و تصور کنید که عملیات زیر را انجام می‌دهیم: یالی از منبع جدید $s'$ به انتهای آن $v$ می‌کشیم، یالی از ابتدای آن $u$ به چاه جدید $t'$ می‌کشیم، خود یال را حذف می‌کنیم، و از چاه قدیمی $t$ به منبع قدیمی $s$ یک یال با ظرفیت بی‌نهایت رسم می‌کنیم. با این اقدامات، ما این واقعیت را شبیه‌سازی می‌کنیم که این یال اشباع شده است - از $v$ یک شار خروجی اضافی به مقدار $d(e)$ وجود خواهد داشت (این را با منبع جدیدی که مقدار صحیح شار را به $v$ تغذیه می‌کند، شبیه‌سازی می‌کنیم)، و $u$ نیز $d(e)$ شار اضافی ارسال خواهد کرد (اما این شار به جای عبور از یال قدیمی، مستقیماً به چاه جدید $t'$ خواهد رفت). شاری با مقدار $d(e)$ که در ابتدا در طول مسیر $s - \dots - u - v - \dots t$ جریان داشت، اکنون می‌تواند مسیر جدید $s' - v - \dots - t - s - \dots - u - t'$ را طی کند. تنها نکته‌ای که در تعریف شبکه جدید ساده‌سازی شده، این است که اگر فرآیند مذکور چندین یال بین یک زوج رأس یکسان ایجاد کند، این یال‌ها در یک یال واحد با ظرفیت مجموعشان ادغام می‌شوند.
شار کمینه¶
توجه داشته باشید که در طول یال $(t, s)$ (از چاه قدیمی به منبع قدیمی) با ظرفیت $\infty$، کل شار شبکه قدیمی متناظر جریان پیدا می‌کند. یعنی، ظرفیت این یال بر مقدار شار شبکه قدیمی تأثیر می‌گذارد. با دادن یک ظرفیت به اندازه کافی بزرگ (یعنی $\infty$) به این یال، شار شبکه قدیمی نامحدود می‌شود. با محدود کردن این یال توسط ظرفیت‌های کوچکتر، مقدار شار کاهش خواهد یافت. اما اگر این یال را با مقداری بیش از حد کوچک محدود کنیم، شبکه یک جواب اشباع‌شده نخواهد داشت، یعنی جواب متناظر برای شبکه اصلی، تقاضای یال‌ها را برآورده نخواهد کرد. بدیهی است که در اینجا می‌توان از جستجوی دودویی برای پیدا کردن کمترین مقداری استفاده کرد که با آن هنوز تمام محدودیت‌ها برآورده می‌شوند. این کار، شار کمینه شبکه اصلی را به ما می‌دهد.