جریان بیشینه: فورد-فالکرسون و قضیه برش-کمینه/جریان-بیشینه

یک شبکه جریان چه چیزی را نشان می‌دهد

یک Flow Network (شبکه جریان) یک گراف جهت‌دار است، همان‌طور که پیش‌تر در این مجموعه معرفی شد، جایی که هر یال یک Capacity (ظرفیت) دارد که محدود می‌کند چقدر "جریان" می‌تواند از میان آن عبور کند، و دو رأس مشخص: یک Source (منبع) s که جریان از آنجا نشأت می‌گیرد، و یک Sink (چاهک) t که جریان در آنجا خاتمه می‌یابد. این سناریوهای واقعی مانند جریان آب از میان لوله‌ها با قطر محدود، جریان داده از میان لینک‌های شبکه با پهنای باند محدود، یا جریان کالا از میان یک زنجیره تأمین با ظرفیت حمل‌ونقل محدود را مدل‌سازی می‌کند.

یک جریان معتبر باید دو ویژگی را برآورده کند:

محدودیت ظرفیت: برای هر یال (u, v)،
  جریان f(u,v) نمی‌تواند از ظرفیتش c(u,v) فراتر رود

حفظ جریان: برای هر رأس به‌جز s و t،
  کل جریان وارد به رأس برابر با
  کل جریان خارج از رأس است
  (جریان نمی‌تواند در هیچ‌جایی به‌جز منبع و چاهک انباشته شود)

مسئله Maximum Flow Problem (جریان بیشینه) اختصاص مقادیر جریان به هر یال را می‌خواهد که کل جریان خارج از منبع را کمینه می‌کند (به‌طور معادل، کل جریان رسیده به چاهک)، در حالی که هر دو محدودیت بالا را رعایت می‌کند.

روش فورد-فالکرسون: یافتن مکرر مسیرهای تقویتی

Ford-Fulkerson Method (روش فورد-فالکرسون) بر یک ایده ساده و شهودی مبتنی است: تا زمانی که یک مسیر از منبع به چاهک وجود دارد که در امتداد آن همچنان جریان بیشتری می‌توان فشار داد، جریان اضافی را در امتداد آن مسیر فشار بده، و تکرار کن تا هیچ مسیری باقی نماند.

گراف باقی‌مانده

ایده ساختاری کلیدی که این روش را درست کار می‌کند Residual Graph (گراف باقی‌مانده) است، که نشان می‌دهد چقدر جریان اضافی همچنان می‌تواند در امتداد هر یال فشار داده شود، و حیاتاً، همچنین توانایی "لغو‌کردن" جریان از‌قبل‌ارسال‌شده، از طریق یک یال معکوس را نشان می‌دهد.

برای یک یال (u, v) با ظرفیت c و جریان فعلی f:
ظرفیت باقی‌مانده رو-به-جلو: c(u,v) - f(u,v)
                            (فضای باقی‌مانده برای فشار جریان بیشتر)
ظرفیت باقی‌مانده رو-به-عقب: f(u,v)
                            (توانایی لغو جریان از‌قبل‌ارسال‌شده)

این مکانیزم یال-معکوس ضروری است: اجازه می‌دهد الگوریتم یک انتخاب غیربهینه پیشین را با به‌طور مؤثر "بازگرداندن" جریان در امتداد یک مسیر و مسیریابی مجدد آن به جای دیگر تصحیح کند، که بدون آن الگوریتم می‌توانست در یک راه‌حل غیربهینه گیر بیفتد.

الگوریتم

FORD-FULKERSON(G, s, t):
  جریان f را روی هر یال به 0 مقداردهی اولیه کن
  تا زمانی که یک مسیر p از s به t در گراف باقی‌مانده Gf وجود داشته باشد:
      حداقل ظرفیت باقی‌مانده در امتداد p را پیدا کن، آن را cf(p) بنام
      // این "گلوگاه" مسیر تقویتی است
      برای هر یال (u, v) در مسیر p:
          اگر (u, v) یک یال رو-به-جلو باشد:
              f(u, v) = f(u, v) + cf(p)
          در غیر این صورت:      // (u, v) یک یال رو-به-عقب است
              f(v, u) = f(v, u) - cf(p)
  f را برگردان

هر چنین مسیری پیداشده در گراف باقی‌مانده Augmenting Path (مسیر تقویتی) نامیده می‌شود، و فشار جریان در امتداد آن به‌طور دقیق کل جریان را به‌اندازه ظرفیت گلوگاه مسیر افزایش می‌دهد — کوچک‌ترین ظرفیت باقی‌مانده در میان همه یال‌های آن مسیر، چون آن یال محدود می‌کند کل مسیر چقدر جریان اضافی می‌تواند حمل کند.

ردیابی یک مثال کوچک

شبکه ساده: s → a (ظرفیت 10)، s → b (ظرفیت 10)
                a → t (ظرفیت 10)، b → t (ظرفیت 10)
                a → b (ظرفیت 1)

تکرار 1: مسیر تقویتی s→a→t، گلوگاه = 10
             جریان: s→a=10، a→t=10، کل جریان تاکنون = 10

تکرار 2: مسیر تقویتی s→b→t، گلوگاه = 10
             جریان: s→b=10، b→t=10، کل جریان تاکنون = 20

هیچ مسیر تقویتی بیشتری وجود ندارد (هر دو a→t و b→t اشباع)
جریان بیشینه = 20

تحلیل زمان اجرا: بهبود ادموندز-کارپ

زمان اجرای روش پایه فورد-فالکرسون به این بستگی دارد که مسیرهای تقویتی چگونه انتخاب می‌شوند، و با انتخاب‌های ضعیف (و ظرفیت‌های گنگ)، ممکن است حتی در تعداد محدودی گام در موارد آسیب‌شناختی پایان نیابد. Edmonds-Karp Algorithm (الگوریتم ادموندز-کارپ) این را با انتخاب خاص کوتاه‌ترین مسیر تقویتی هر بار، پیداشده با استفاده از جستجوی سطح‌اول که پیش‌تر در این مجموعه بحث شد، رفع می‌کند.

استفاده از BFS برای یافتن کوتاه‌ترین مسیر تقویتی
هر تکرار تضمین می‌کند الگوریتم در یک تعداد محدود
از تکرارها پایان می‌یابد:

زمان اجرای کل: O(VE²)

این به این دلیل است که هر یال فقط می‌تواند O(V) بار
گلوگاه یک کوتاه‌ترین مسیر تقویتی شود پیش از اینکه
طول کوتاه‌ترین مسیر باید به‌طور دقیق افزایش یابد،
و فقط O(V) طول مسیر ممکن