مسئله بیشینه جریان

مسئله بیشینه جریان مسئله یافتن بیشینه جریان (از نظر ارزش جریان) از یک منبع واحد به یک مقصد واحد است.

محتویات

۱ مسئله
۲ الگوریتم
۳ منابع
۴ جستارهای وابسته

مسئله [ویرایش]

گراف (G(V،G همبند با یالهای جهت دار با یال‌های وزن‌دار (c(u،v با یک رأس منبع $s$ و یک رأس مقصد $t$ . وزن هر یال برابر ظرفیت آن یال است. ۱-جریان از هر یال نباید بیشتر از ظرفیت یال باشد. ۲-برای هر رأس جز منبع و مقصد جریان ورودی برابر با جریان خروجی است. بیشینه کردن مجموع وزن یال‌های خروجی از مبدأ –مجموع وزن یال‌های ورودی به مبدأ (یا مجموع وزن یال‌های ورودی به مقصد–مجموع وزن یال‌های خروجی از مقصد). روش‌های مختلفی برای حل این مسئله وجود دارد.

الگوریتم [ویرایش]

یک الگوریتم حریصانه جریان را از جمع کردن جریان‌های از منبع به مقصد به صورت تکرار شونده می‌سازد. در ابتدا هر یال وزن اولیه خودش را دارد (ظرفیت استفاده نشده از یال‌ها). مسیری از منبع به مقصد از یال‌های غیر صفر پیدا می‌کنیم. برای هر یال در طول مسیر بیشترین جریان گذرنده از مسیر را از ظرفیت یال کم می‌کنیم.و به معکوس یال اضافه می‌کنیم. تا وقتی که مسیری پیدا نشود ادامه می‌دهیم. مسئله تمام می‌شود چون هر بار حداقل یک واحد به جریان اضافه می‌شود.

روش	پیچیدگی	توضیح
الگوریتم فورد-فالکرسون	$\scriptstyle O(E \cdot \mathit{maxflow})$	از آن جایی که مسیر بازی در گراف باقی مانده وجود دارد.کمینه ظرفیت‌های گراف باقی مانده را به وسیله مسیر می‌فرستد.این الگوریتم فقط زمانی کار می‌کند که همه وزن‌ها عدد صحیح باشند.در غیر این صورت این الگوریتم مقدار بیشینه را بر نمی‌گرداند.
الگوریتم Edmonds Karp	$(O(VE^2$	یک تخصص این الگوریتم پیدا کردن مسیرهای اضافه شده به وسیله جستجوی سطح اول است.
الگوریتم Dinitz blocking flow	$(O(V^2 E$	در هر مرحله این الگوریتم گراف لایه‌ای را به وسیله جستوجوی اول سطح روی باقیمانده گراف می‌سازد.بیشینه جریان در یک گراف لایه‌ای در (O(VE محاسبه می‌شود و بیشترین تعداد مرحل n-1 است.
الگوریتم General push-relabel	$(O(V^2E$	الگوریتم push relabel از یک پیش جریان پشتیبانی می‌کند.برای مثال یک تابع جریان با امکان افزایش در رأس‌ها.الگوریتم اجرا تا وقتی که رأسی با افزایش مثبت وجود دارد اجرا می‌شود.برای مثال یک رأس فعال در گراف.عمل push جریان را روی یک یال اضافه افزایش می‌دهد.و یک تابع ارتفاع روی رأس‌ها کنترل می‌کند که کدام یال باقیمانده می‌تواند push شود.این توابع تضمین می‌کنند که جریان باقیمانده بیشینه‌است.
الگوریتم General push-relabel همراه با FIFO vertex selection rule	$(O(V^3$	این الگوریتم همواره آخرین رأس فعال را انتخاب می‌کند و عمل push را انجام می‌دهد تا زمانی که افزایش مثبت است یا یک یال باقیمانده مجاز از این رأس وجود دارد.
الگوریتم Dinitz blocking flow به همراه درخت پویا	$((O(VE\log(V$	داده ساختار درخت پویا سرعت محاسبه بیشینه جریان را در گراف لایه‌ای افزایش می‌دهد.
Push-relabel algorithm with using dynamic trees	$((O(VE\log(V^2/E$	این الگوریتم درختی با اندازه محدود می‌سازد روی باقیمانده گراف راجع به تابع ارتفاع می‌سازد.این درخت‌ها عمل push چند سطحی را تأمین می‌کنند.
Binary blocking flow algorithm ^[۱]	$\scriptscriptstyle O(E\min(V^{2/3},\sqrt{E})\log(V^2/E)\log{U})$	مقدار U وابسته‌است به بیشینه ظرفیت شبکه. .