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

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

परिभाषा

दिया गया प्रवाह नेटवर्क $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})$ से $t_{i}$ तक वस्तु $i$ के लिए $d_{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$ है, और $l(t,s)=u(t,s)=1$ और $c(t,s)=0$ के साथ एक किनारा $(t,s)$ जोड़ें
• सभी जोड़े सबसे छोटा पथ - सभी क्षमताओं को असीमित होने दें, और $v(v-1)/2$ वस्तुओं के लिए 1 का प्रवाह खोजें, प्रत्येक जोड़ी नोड्स के लिए एक है ।