परिसंचरण समस्या

परिसंचरण समस्या और इसके प्रकार प्रवाह नेटवर्क समस्याओं का एक सामान्यीकरण हैं, जिसमें किनारे के प्रवाह पर निचली सीमा की अतिरिक्त बाधा होती है, और स्रोत और सिंक के लिए प्रवाह संरक्षण भी आवश्यक होता है (यानी कोई विशेष नोड नहीं होते हैं)। समस्या के भिन्न रूप में, नेटवर्क के माध्यम से कई वस्तुओं का प्रवाह होता है, और प्रवाह पर लागत होती है।

परिभाषा

दिया गया प्रवाह नेटवर्क $G(V,E)$ साथ:

$l(v,w)$, नोड से प्रवाह पर निचली सीमा $v$ नोड करने के लिए $w$,

$u(v,w)$, नोड से प्रवाह पर ऊपरी सीमा $v$ नोड करने के लिए $w$,

$c(v,w)$, प्रवाह की एक इकाई की लागत $(v,w)$

और बाधाएँ:

$l(v,w)\leq f(v,w)\leq u(v,w)$,

$\sum _{w\in V}f(u,w)=0$ (प्रवाह नोड्स में प्रकट या गायब नहीं हो सकता)।

बाधाओं को संतुष्ट करने वाले प्रवाह असाइनमेंट को खोजने से दी गई परिसंचरण समस्या का समाधान मिलता है।

समस्या के न्यूनतम लागत संस्करण में, न्यूनतम करें

$\sum _{(v,w)\in E}c(v,w)\cdot f(v,w).$

मल्टी-कमोडिटी सर्कुलेशन

बहु-वस्तु परिसंचरण समस्या में, आपको व्यक्तिगत वस्तुओं के प्रवाह पर भी नज़र रखने की आवश्यकता है:

$\,f_{i}(v,w)$	The flow of commodity $i$ from $v$ to $w$.
$\,f(v,w)=\sum _{i}f_{i}(v,w)$	The total flow.

वस्तु के प्रत्येक प्रवाह पर एक निचली सीमा भी होती है।

$\,l_{i}(v,w)\leq f_{i}(v,w)$

वस्तुओं के लिए संरक्षण बाधा को व्यक्तिगत रूप से बरकरार रखा जाना चाहिए:

$\ \sum _{w\in V}f_{i}(u,w)=0.$

समाधान

परिसंचरण समस्या के लिए, कई बहुपद एल्गोरिदम विकसित किए गए हैं (उदाहरण के लिए, एडमंड्स-कार्प एल्गोरिदम, 1972; टार्जन 1987-1988)। टार्डोस ने पहला दृढ़तापूर्वक बहुपद एल्गोरिथ्म पाया। एकाधिक वस्तुओं के मामले में, समस्या पूर्णांक प्रवाह के लिए एनपी-पूर्ण है। भिन्नात्मक प्रवाह के लिए, यह बहुपद समय में हल करने योग्य है, क्योंकि कोई समस्या को रैखिक प्रोग्रामिंग के रूप में तैयार कर सकता है।

संबंधित समस्याएँ

नीचे कुछ समस्याएं दी गई हैं, और ऊपर दिए गए सामान्य सर्कुलेशन सेटअप के साथ उन्हें कैसे हल किया जाए।

• न्यूनतम लागत मल्टी-कमोडिटी सर्कुलेशन समस्या - ऊपर दिए गए सभी बाधाओं का उपयोग करना।
• न्यूनतम लागत संचलन समस्या - एक ही वस्तु का उपयोग करें
• मल्टी-कमोडिटी सर्कुलेशन - लागत को अनुकूलित किए बिना हल करें।
• सरल परिचालन - बस एक वस्तु का उपयोग करें, और कोई कीमत नहीं।
• बहु-वस्तु प्रवाह समस्या|बहु-वस्तु प्रवाह - यदि $K_{i}(s_{i},t_{i},d_{i})$ की मांग को दर्शाता है $d_{i}$ वस्तु के लिए $i$ से $s_{i}$ को $t_{i}$, बढ़त बनायें $(t_{i},s_{i})$ साथ $l_{i}(t_{i},s_{i})=u(t_{i},s_{i})=d_{i}$ सभी वस्तुओं के लिए $i$. होने देना $l_{i}(u,v)=0$ अन्य सभी किनारों के लिए.
• न्यूनतम लागत बहु-वस्तु प्रवाह समस्या - जैसा कि ऊपर बताया गया है, लेकिन लागत कम से कम करें।
• न्यूनतम लागत प्रवाह समस्या - ऊपर के अनुसार, 1 वस्तु के साथ।
• अधिकतम प्रवाह समस्या - सभी लागतों को 0 पर सेट करें, और सिंक से एक किनारा जोड़ें $t$ स्रोत के लिए $s$ साथ $l(t,s)=0$, $u(t,s)=$∞ और $c(t,s)=-1$.
• न्यूनतम लागत अधिकतम प्रवाह समस्या - सबसे पहले अधिकतम प्रवाह राशि ज्ञात करें $m$. फिर हल करें $l(t,s)=u(t,s)=m$ और $c(t,s)=0$.
• सबसे छोटा पथ समस्या|एकल-स्रोत सबसे छोटा पथ - चलो $l(u,v)=0$ और $c(u,v)=1$ ग्राफ़ में सभी किनारों के लिए, और एक किनारा जोड़ें $(t,s)$ साथ $l(t,s)=u(t,s)=1$ और $c(t,s)=0$.
• सबसे छोटा पथ समस्या|सभी युग्मों में सबसे छोटा पथ - सभी क्षमताएं असीमित हों, और 1 का प्रवाह ज्ञात करें $v(v-1)/2$ कमोडिटी, नोड्स की प्रत्येक जोड़ी के लिए एक।