Network flow problem
مشترکہ اصلاح میں، نیٹ ورک کے بہاؤ کے مسائل کمپیوٹیشنل مسائل کی ایک کلاس ہیں جس میں ان پٹ ایک بہاؤ نیٹ ورک ہے (اس کے کناروں پر عددی صلاحیتوں کے ساتھ ایک گراف)، اور مقصد ایک بہاؤ، ہر کنارے پر عددی اقدار کی تعمیر کرنا ہے جو صلاحیت کی رکاوٹوں کا احترام کرتا ہے اور جس میں آنے والا بہاؤ کچھ مخصوص ٹرمینلز کے علاوہ تمام عمودی حصوں پر باہر جانے والے بہاؤ کے برابر ہوتا ہے۔ نیٹ ورک کے بہاؤ کے مسائل کی مخصوص اقسام میں شامل ہیں: زیادہ سے زیادہ بہاؤ کا مسئلہ، جس میں مقصد ماخذ ٹرمینلز سے اور سنک ٹرمینلز میں بہاؤ کی کل مقدار کو زیادہ سے زیادہ کرنا ہے۔ کم سے کم لاگت کے بہاؤ کا مسئلہ، جس میں کناروں کی لاگت کے ساتھ ساتھ صلاحیتیں بھی ہوتی ہیں اور مقصد ایک دی گئی مقدار میں بہاؤ (یا زیادہ سے زیادہ بہاؤ) حاصل کرنا ہوتا ہے جس کی کم سے کم ممکنہ لاگت ہوتی ہے۔ کثیر اجناس کے بہاؤ کا مسئلہ، جس میں کسی کو مختلف اجناس کے لیے متعدد بہاؤ بنانا ہوتا ہے جن کی کل بہاؤ کی مقدار ایک ساتھ صلاحیتوں کا احترام کرتی ہے۔ کہیں بھی صفر بہاؤ، امتزاج میں زیر مطالعہ بہاؤ کی ایک قسم جس میں بہاؤ کی مقدار غیر صفر اقدار کے ایک محدود سیٹ تک محدود ہوتی ہے۔ زیادہ سے زیادہ بہاؤ کی قدر قدر کے برابر ہوتی ہے۔ لگ بھگ میکس فلو من کٹ تھیوریمز ملٹی کموڈٹی فلو کے مسائل کے لیے اس نتیجے کی توسیع فراہم کرتے ہیں۔ غیر ہدایت شدہ بہاؤ نیٹ ورک کا گوموری-ہو درخت ٹرمینل عمودی کے مختلف جوڑوں کے درمیان تمام کم از کم کٹوتیوں کی ایک جامع نمائندگی فراہم کرتا ہے۔ بہاؤ کی تعمیر کے لیے الگورتھم میں ڈینک کا الگورتھم، زیادہ سے زیادہ بہاؤ کے لیے ایک مضبوط کثیر الجہتی الگورتھم شامل ہے۔ ایڈمنڈز-کارپ الگورتھم، زیادہ سے زیادہ بہاؤ کے لیے ایک تیز مضبوط کثیر الجہتی الگورتھم۔ فورڈ-فلکرسن الگورتھم، زیادہ سے زیادہ بہاؤ کے لیے ایک لالچی الگورتھم جو عام طور پر مضبوط کثیر الجہتی نہیں ہے۔ نیٹ ورک سمپلیکس الگورتھم، لکیری پروگرامنگ پر مبنی ایک طریقہ ہے لیکن نیٹ ورک کے بہاؤ کے لیے خصوصی ہے۔ کم سے کم لاگت والے الگورتھم کے بہاؤ کے لیے کلومیٹر سے باہر کا طریقہ۔ پش-لیبل زیادہ سے زیادہ بہاؤ الگورتھم، زیادہ سے زیادہ بہاؤ کے لیے سب سے موثر معروف تکنیکوں میں سے ایک ہے۔ بصورت دیگر اس مسئلے کو زیادہ روایتی لکیری پروگرام یا اسی طرح کے حل کار کا استعمال کرتے ہوئے حل کیا جا سکتا ہے۔ گراف الگورتھم مشترکہ اصلاح ہدایت شدہ گراف