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