Network flow problem
संयोजन अनुकूलन में, नेटवर्क प्रवाह समस्याएं कम्प्यूटेशनल समस्याओं का एक वर्ग है जिसमें इनपुट एक प्रवाह नेटवर्क है (इसके किनारों पर संख्यात्मक क्षमताओं के साथ एक ग्राफ), और लक्ष्य एक प्रवाह का निर्माण करना है, प्रत्येक किनारे पर संख्यात्मक मान जो क्षमता बाधाओं का सम्मान करते हैं और जिसमें आने वाला प्रवाह कुछ निर्दिष्ट टर्मिनलों को छोड़कर सभी शीर्षों पर बहिर्गामी प्रवाह के बराबर होता है। नेटवर्क प्रवाह समस्याओं के विशिष्ट प्रकारों में शामिल हैंः अधिकतम प्रवाह समस्या, जिसमें लक्ष्य स्रोत टर्मिनलों से और सिंक टर्मिनलों में प्रवाह की कुल मात्रा को अधिकतम करना है न्यूनतम-लागत प्रवाह समस्या, जिसमें किनारों की लागत के साथ-साथ क्षमता भी होती है और लक्ष्य प्रवाह की दी गई मात्रा (या अधिकतम प्रवाह) को प्राप्त करना है जिसमें न्यूनतम संभव लागत होती है बहु-वस्तु प्रवाह समस्या, जिसमें किसी को विभिन्न वस्तुओं के लिए कई प्रवाहों का निर्माण करना होता है जिनकी कुल प्रवाह मात्रा एक साथ क्षमताओं का सम्मान करती है कहीं भी-शून्य प्रवाह, संयोजन में अध्ययन किया जाने वाला एक प्रकार का प्रवाह जिसमें प्रवाह मात्रा गैर-शून्य मूल्यों के एक सीमित सेट तक सीमित होती है अधिकतम-प्रवाह न्यूनतम-कटौती प्रमेय मूल्य के लिए अधिकतम प्रवाह के मूल्य के बराबर होता है। अनुमानित अधिकतम-प्रवाह न्यूनतम-कटौती प्रमेय बहु-वस्तु प्रवाह समस्याओं के लिए इस परिणाम का विस्तार प्रदान करते हैं। एक दिशाहीन प्रवाह नेटवर्क का गोमोरी-हू वृक्ष अंतिम शीर्षों के विभिन्न जोड़े के बीच सभी न्यूनतम कटौती का एक संक्षिप्त प्रतिनिधित्व प्रदान करता है। प्रवाह के निर्माण के लिए एल्गोरिदम में शामिल हैं डिनिक का एल्गोरिदम, अधिकतम प्रवाह के लिए एक मजबूत बहुपद एल्गोरिदम एडमंड्स-कार्प एल्गोरिदम, अधिकतम प्रवाह के लिए एक तेज दृढ़ता से बहुपद एल्गोरिदम फोर्ड-फुल्करसन एल्गोरिदम, अधिकतम प्रवाह के लिए एक लालची एल्गोरिदम जो सामान्य रूप से दृढ़ता से बहुपद नहीं है नेटवर्क सिम्प्लेक्स एल्गोरिदम, रैखिक प्रोग्रामिंग पर आधारित एक विधि है लेकिन नेटवर्क प्रवाह के लिए विशिष्ट है एल्गोरिदम-लागत प्रवाह के लिए किलोमीटर से बाहर पुश-रीलेबल अधिकतम प्रवाह एल्गोरिदम, अधिकतम प्रवाह के लिए सबसे कुशल ज्ञात तकनीकों में से एक अन्यथा समस्या को अधिक पारंपरिक रैखिक कार्यक्रम या इसी तरह के समान के रूप में तैयार किया जा सकता है और एक सामान्य उद्देश्य अनुकूलन समाधानक का उपयोग करके हल किया जा सकता है। ग्राफ एल्गोरिदम संयोजन अनुकूलन निर्देशित ग्राफ