المپدیا

شبکه به یک گراف جهت‌دار وزن‌دار می‌گویند. به وزن یال ها در مسئله شار ظرفیت آن یال (capacity) نیز گفته میشود.

شار یک تابع روی یک شبکه است که به هر یال آن یک عدد می‌دهد که به آن مقدار جریان آن یال نیز می‌گوییم. هدف ما رساندن مقداری جریان از راس منبع به راس مقصد می‌باشد به طوری که ۳ شرط زیر حفظ شوند:

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

برش در یک شبکه را به این صورت تعریف می‌کنیم. راس‌های گراف را به دو زیر مجموعه A و B افراز کرده به‌طوری که راس منبع در بخش A باشد و راس مقصد در بخش B. جمع ظرفیت تمام یال‌هایی که از A به B میروند را اندازه آن برش می‌نامیم.

اندازه شار بیشینه با برش کمینه برابر است.

برای این کار ابتدا ثابت میکنیم اندازه شار بیشینه از برش کمینه بیشتر نیست. سپس با استفاده از کاربرد مسیر افزایشی نشان میدهیم اندازه برش کمینه نمی‌تواند از شار بیشینه بیشتر باشد پس نتیجه می‌شود این دو با‌هم برابرند.
راه حل قسمت اول ساده‌تر است. به‌این‌ صورت که برش کمینه را در نظر بگیرید، از آنجا که راس منبع و مقصد در دو طرف این برش قرار دارند، هر واحد شاری که بخواهد به مقصد برود باید از یکی از یال‌های برش خورده رد شود. پس اندازه‌ی شار نمی‌تواند بیشتر از کمترین برش باشد. پس بزرگترین شار بیشتر از کوچکترین برش نمی‌تواند باشد.
برای قسمت دوم ابتدا مسیر افزایشی را تعریف میکنیم. مسیر افزایشی مسیری در گراف زمینه است که از راس s شروع و به راس t ختم میشود.‌ (یاد آوری‌. گراف زمینه گرافی بدون جهت است که از برداشتن جهت‌های گراف اصلی تشکیل می‌شود.) اگر راس‌های مسیر افزایشی را از چپ به راست بنویسیم به‌طوری که منبع سمت چپ و مقصد سمت راست باشد،‌ تعدادی یال از چپ به راست (رو به جلو) و تعدادی از راست به چپ (رو به عقب) هستند. مسیر افزایشی ما درست است اگر و فقط اگر هر یال رو به جلو مقدار جریانش از ظرفیتش اکیدن کمتر باشد و هر یال رو به عقب مقدار جریانش مثبت باشد.
حال نشان می‌دهیم اگر چنین مسیری وجود داشته باشد می‌توان اندازه شار را یک واحد افزایش داد به این صورت که جریان هر یال رو به جلو را یک واحد زیاد کرده و جریان هر یال رو به عقب را یک واحد کم می‌کنیم. برای همه‌ی راس های مسیر شرایط شار همچنان برقرار است زیرا اگر یال رو به جلو باشد با افزایش شار یال مقدار جریان یک واحد به سمت جلو حرکت میکند و اگر یال رو به عقب باشد مقدار جریان را یک واحد که کم کنیم یک واحد جریان که قبلن به سمت عقب میرفت دیگر نمی‌رود و باز هم جریان یک واحد به سمت جلو حرکت میکند.
حال می‌دانیم اگر شاری مسیر افزایشی داشته باشد میتوان اندازه‌ی آن شار را یک واحد افزایش داد. حال با استفاده از این تعریف مسئله اصلی را حل میکنیم.
می‌خواهیم نشان دهیم شار بیشینه (که مسیر افزایشی ندارد) اندازه‌اش از کمترین برش بیشتر است. برای این کار راس منبع و تمام راس هایی که منبع به آنها مسیر نیمه افزایشی دارد را در دسته A قرار دهید (مسیر نیمه افزایشی مسیری است که خاصیت های مسیر افزایشی را دارد اما به راس مقصد ختم نمیشود) و تمام راس‌های دیگر را در دسته B قرار دهید. میدانیم ظرفیت تمام یال‌هایی که از A به B می‌روند تکمیل است چرا که اگر یکی از آن‌ها هنوز ظرفیت داشته باشد می‌توان به راس دیگر آن یال نیز مسیر نیمه‌افزایشی داشت (منظور از ظرفیت تکمیل یک یال برابر بودن جریان آن یال با ظرفیتش می‌باشد). همچنین میدانیم تمام یال‌هایی که از B به A می‌آیند جریانشان صفر است چرا که اگر جریانی داشته باشند مسیر افزایشی‌ای به سر دیگر آن یال پیدا می‌شود. از آنجا که هیچ جریانی از ‌‌‌B به A بر نمی‌گردد پس اندازه‌ی شار بیشینه با اندازه این برش برابر است. پس اندازه ماکسیمم شار از کمترین برش بیشتر است.

الف) میتوان نشان داد مقدار شار بیشینه با ظرفیت های صحیح مقداری صحیح است.
ب) میتوان نشان داد اگر در شاری مسیر افزایشی وجود نداشته باشد آن شار بیشینه است.