موضوع مقاله: مسئله بیشینه جریان | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسئله بیشینه جریان | مقدمه: در تئوری بهینه‌سازی، مسائل بیشینه جریان شامل پیدا کردن یک جریان عملی بیشینه از داخل یک شبکهٔ جریان تک-مبدأ و تک-مقصد است. | ## بخش 1: مسئله بیشینه جریان | می‌توان به مسئلهٔ بیشینه جریان، به صورت حالت خاصی از مسائل پیچیده‌تر شبکهٔ جریان، مانند مسئلهٔ گردش، نگاه کرد. مقدار ماکسیمم یک جریان s-t (جریان از مبدأ به مقصد) برابر حداقل ظرفیت یک برش s-t (برشی که مبدأ را از مقصد جدا می‌کند) در شبکه است، همان‌طور که در قضیهٔ جریان بیشینه-برش کمینه ذکر شده است. Ross در سال ۱۹۵۴ به عنوان مدل ساده شده‌ای از جریان رفت و آمد خط آهن شوروی مطرح شد. ظرفیت یک یال، نگاشت است که با یا نمایش داده می‌شود، و نشان دهندهٔ بیشینه مقدار جریانی است که می‌تواند از یال بگذرد. یک جریان، نگاشت است که با یا نمایش داده می‌شود و دارای دو شرط زیر است: به ازای هر (شرط ظرفیت: جریان یک یال نمی‌تواند از ظرفیتش بیشتر باشد) به ازای هر (بقای جریان‌ها: جمع جریان‌های ورودی یک رأس باید با جمع جریان‌های خروجی از آن برابر باشد، به جز در رأس‌های مبدأ و مقصد) مقدار جریان به صورت تعریف می‌شود که ، مبدأ است. راه‌حل‌ها می‌توان گراف باقیمانده را تعریف کرد تا راهی اصولی برای جستجو کردن عملیات‌های جلو-عقب برای یافتن بیشینه جریان فراهم کند. اگر شبکهٔ جریان و جریان روی را داشته باشیم، ، گراف باقیماندهٔ را با توجه به اینگونه تعریف می‌کنیم: مجموعه رأس‌های همانند است. الگوریتم فورد-فالکرسون تا جایی که مسیری باز در گراف باقی مانده وجود دارد، کمینه ظرفیت‌های گراف باقی مانده را به مسیر می‌فرستد. این الگوریتم فقط زمانی کار می‌کند که همه وزن‌ها عدد صحیح باشند، در غیر این صورت ممکن است مقدار بیشینه برگردانده نشود. الگوریتم سد جریان Dinitz این الگوریتم در هر مرحله یک گراف لایه‌ای را به وسیله جستجوی سطح اول روی گراف باقیمانده می‌سازد. بیشینه جریان در یک گراف لایه‌ای در (O(VE محاسبه می‌شود، و بیشترین تعداد مرحل n-1 است. الگوریتم ارسال-برچسب عمومی الگوریتم ارسال-برچسب از یک پیش‌جریان (یک تابع جریان با امکان افزایش در رأس‌ها) پشتیبانی می‌کند. الگوریتم اجرا تا وقتی که رأسی با افزایش مثبت (یک رأس فعال در گراف) وجود دارد اجرا می‌شود. عمل push جریان را روی یک یال باقیمانده افزایش می‌دهد، و یک تابع ارتفاع روی رأس‌ها کنترل می‌کند که کدام یال باقیمانده می‌تواند push شود. استفادهٔ درست از این توابع تضمین می‌کنند که جریان به دست آمده یک جریان بیشینه است. الگوریتم ارسال-برچسب عمومی همراه با قانون انتخاب رأس FIFO این الگوریتم همواره آخرین رأس فعال را انتخاب می‌کند و عمل push را تا زمانی که افزایش مثبت است یا یک یال باقیمانده مجاز از این رأس وجود دارد، انجام می‌دهد. الگوریتم سد جریان Dinitz به همراه درخت پویا داده ساختار درخت پویا سرعت محاسبه بیشینه جریان را در گراف لایه‌ای تا افزایش می‌دهد. الگوریتم ارسال-برچسب عمومی همراه با درخت پویا این الگوریتم با توجه به تابع ارتفاع، درختی با اندازه محدود روی گراف باقی‌مانده می‌سازد. قضیهٔ جریان انتگرال قضیهٔ جریان انتگرال می‌گوید: اگر هر یال در شبکهٔ جریان ظرفیت انتگرالی داشته باشد، آنگاه یک جریان ماکسیمال انتگرالی وجود دارد. | ## بخش 2: مسئله بیشینه جریان | تبدیل یک مسئلهٔ بیشینه جریان چند-مبدأ چند-مقصد به یک مسئلهٔ بیشینه جریان تک-مبدأ تک-مقصد. می‌خواهیم جریان بیشینه را روی شبکهٔ که دارای مجموعهٔ مبدأهای و مجموعهٔ مقصدهای (به جای تنها یک مبدأ و یک مقصد) است، پیدا کنیم. می‌توانیم مسئله چند-مبدأ و چند-مقصد را با افزودن یک مبدأ تثبیت شده که به تمام راس‌های متصل است و یک مقصد تثبیت شده که به تمام راس‌های متصل است (ابرمبدأ و ابرمقصد) و یال‌های آن‌ها ظرفیت بی‌نهایت دارند، به یک مسئلهٔ بیشینه جریان تبدیل کنیم. کمینه پوشش مسیر در گراف جهت‌دار بدون دور برای پیدا کردن کمینه تعداد مسیر‌ها برای پوشش دادن تمام رأس‌های در یک گراف جهت‌دار بدون دور ، می‌توانیم یک گراف دوبخشی از بسازیم که: که درجهٔ خروجی هر مثبت است. آنگاه می‌توان با استفاده از نظریه کونیگ نشان داد که یک تطابق با اندازهٔ دارد اگر و تنها اگر راه وجود داشته باشد که هر رأس در را پوشش می‌دهد و تعداد رأس‌های است؛ بنابراین مسئله را می‌توان با پیدا کردن تطابق ماکسیمم در حل کرد. برای پیدا کردن تطابق بیشینه (تطابقی که بیش‌ترین تعداد رأس‌های ممکن را دارد) در یک گراف دو بخشی ، می‌توانیم مسئله را با ساختن شبکهٔ به یک مسئلهٔ بیشینه جریان تبدیل کنیم، که: شامل یال‌هایی از است که جهتشان از به است. تبدیل یک مسئلهٔ تطابق بیشینهٔ جریان با شرط ظرفیت رأس‌ها به مسئلهٔ بیشینه جریان اصلی با بخش کردن رأس‌ها. اگر شبکهٔ را داشته باشیم که در آن علاوه بر یال‌ها، هر رأس هم ظرفیت دارد، یعنی نگاشت که با نمایش داده می‌شود به طوری که جریان f علاوه بر شرط ظرفیت و بقای جریان‌ها، شرط ظرفیت رأس را هم داشته باشد: به بیان دیگر مقدار جریانی که از یک رأس می‌گذرد نمی‌تواند از ظرفیت آن بیشتر باشد. برای یافتن ماکسیمم جریان در می‌توان با گسترش ، مسئله را به یک مسئلهٔ بیشینه جریان تبدیل کرد. ابتدا هر با و جایگزین می‌شود که متصل به یال‌هایی است که به وارد می‌شود و متصل به یال‌هایی است که از آن خارج می‌شوند، سپس ظرفیت را به یالی نسبت می‌دهیم که و را شامل می‌شود (شکل ۴٫۴٫۱ را ببینید، ولی در نظر داشته باشید که جای و به اشتباه در آن جابه‌جا شده‌است). در این شبکهٔ گسترش یافته، شرط ظرفیت رأس برداشته شده است؛ بنابراین می‌توان با این مسئله مانند یک مسئلهٔ بیشینه جریان برخورد کرد. برای پیدا کردن بیشینه تعداد راه‌های مستقل از دو رأس به در گراف جهت‌دار ، می‌توان از دارای ظرفیت رأس، شبکهٔ را ساخت به طوری که: و به ترتیب مبدأ و مقصد اند. بیشینه مسیر یال‌مجزا برای پیدا کردن بیشینه تعداد مسیرهای یال‌مجزا از رأس به رأس در گراف جهت دار ، می‌توان مسئله را با ساختن شبکهٔ از با مبدأ و مقصد و نسبت دادن جریان واحد به هر یال، به یک مسئلهٔ بیشینه جریان تبدیل کرد. بیشینه مسیر رأس‌مجزا برای پیدا کردن بیشینه تعداد مسیرهای رأس‌مجزا از رأس به رأس در گراف جهت‌دار ، می‌توان مسئله را با ساختن شبکهٔ به صورت زیر، به یک مسئلهٔ بیشینه جریان تبدیل کرد: هر رأس در گراف را به دو رأس و تقسیم کنید. در یک مرحلهٔ خاص، تعداد بردها، تعداد بازی‌های باقی‌مانده برای تیم ام، و تعداد بازی‌های باقی‌مانده در مقابل تیم ام است. یک رأس را به طوری که به گراف اضافه می‌کنیم و آن را با یالی با ظرفیت به وصل می‌کنیم که تعداد بازی‌های بین دو تیم و را نشان می‌دهد. هم چنین برای هر تیم یک رأس ایجاد می‌کنیم و هر رأس را به رأس‌های و وصل می‌کنیم تا تضمین کنیم یکی از آن‌ها برنده می‌شود. ادعا می‌کنیم تیم حذف نمی‌شود اگر و تنها اگر اندازهٔ جریانی با مقدار در شبکهٔ وجود داشته باشد. برنامه‌ریزی خطوط هوایی یکی از مسائل مهم در صنایع خطوط هوایی، برنامه‌ریزی برای خدمهٔ پرواز است. | ## بخش 3: مسئله بیشینه جریان | مسائل برنامه‌ریزی در خطوط هوایی می‌تواند به عنوان کاربردی از تعمیم مسئلهٔ بیشینهٔ جریان مطرح شود. ورودی مسئله، مجموعه‌ای از پروازها است که شامل مکان و زمان پروازهای ورودی و خروجی است. در یک مدل از برنامه‌ریزی، هدف این است که یک برنامه‌ریزی عملی صورت گیرد به طوری که حداکثر خدمه فعالیت کنند. برای حل این مسئله، از مدل متفاوتی از مسئلهٔ گردش به نام گردش کراندار استفاده می‌کنیم، که مدل کلی‌ای از مسئلهٔ جریان است که در آن برای حداقل جریان منحصر با یال‌ها محدودیت قائل می‌شویم. هم چنین یال‌های زیر را به اضافه می‌کنیم: یال‌هایی با ظرفیت [۰٬۱] بین و هر یال‌هایی با ظرفیت [۰٬۱] بین هر و یال‌هایی با ظرفیت [۰٬۱] بین هر جفت و یال‌هایی با ظرفیت [۰٬۱] بین هر و ، اگر بتوانیم با صرف هزینه و زمان معقول از به برسیم. یالی با ظرفیت [∞,۰] بین و در روش ذکر شده، ادعا و اثبات می‌شود که پیدا کردن یک جریان با مقدار بین و در ، همان پیدا کردن برنامه‌ای عملی برای مجموعهٔ پروازهای با حداکثر خدمه است. نوع دیگری از برنامه‌ریزی خطوط هوایی، پیدا کردن حداقل خدمه برای انجام شدن تمامی پروازهاست. برای پیدا کردن جواب این مسئله، یک گراف دو قسمتی می‌سازیم که هر پرواز یک کپی در مجموعهٔ و مجموعهٔ دارد. یک تطابق در شامل یک برنامه برای است و بدیهی است که حداکثر تطابق دوقسمتی در این گراف، یک برنامهٔ هوایی با حداقل تعداد خدمه را نشان می‌دهد. همان‌طور که در قسمت کاربردهای این مقاله ذکر شد، پیدا کردن تطابق بیشینه دوبخشی یکی از کاربردهای مسئلهٔ بیشینهٔ جریان است. مسئلهٔ تقاضای گردش تعدادی کارخانه هستند که کالا تولید می‌کنند و تعدادی دهکده هستند که باید به آن‌ها کالا برسد. آن‌ها با شبکه‌ای از جاده‌ها به هم متصل اند که هر جاده ظرفیت برای بیشینه کالایی که می‌تواند از آن بگذرد دارد. این مسئله می‌تواند به یک مسئلهٔ بیشینه جریان تبدیل شود: یک رأس مبدأ اضافه کنید و یال‌هایی از آن به هر رأس کارخانه با ظرفیت تولید اضافه کنید، که آهنگ تولید کارخانهٔ است. یک رأس مقصد اضافه کنید و یال‌هایی از هر رأس دهکده با ظرفیت به آن اضافه کنید، که میزان تقاضای دهکده است. گردشی وجود دارد که تقاضا را برآورده کند اگر و تنها اگر: اگر یک گردش وجود داشته باشد، مسئلهٔ بیشینه جریان جواب این که چه مقدار کالا برای برآورده شدن تقاضا باید از طریق یک جادهٔ خاص فرستاده شود را به ما می‌دهد. عدالت در اشتراک اتومبیل مسئله این است که نفر از یک ماشین در روز به صورت اشتراکی استفاده می‌کنند. هدف ما این است که عادلانه تصمیم بگیریم که در یک روز مشخص، چه کسی رانندگی می‌کند. راه حل به این صورت است: می‌توانیم بر اساس تعداد افرادی که از ماشین استفاده می‌کنند تصمیم بگیریم، یعنی اگر نفر از ماشین در یک روز استفاده می‌کنند، هر نفر به مقدار مسئولیت دارد؛ بنابراین برای هر شخص ، اجبار رانندگی به صورتِ ذکر شده است؛ بنابراین، شخص فقط باید بار در روز رانندگی کند. برای این منظور همان‌طور که در شکل نشان داده شده است، سعی می‌کنیم مسئله را به یک شبکه تبدیل کنیم. | ## جمع‌بندی | حال می‌توان ثابت کرد که اگر جریان وجود داشته باشد، آنگاه چنین وضعیت عادلانه‌ای و چنین جریانی با مقدار همواره وجود دارد.