Network flow problem
સંયુક્ત ઓપ્ટિમાઇઝેશનમાં, નેટવર્ક પ્રવાહ સમસ્યાઓ એ કોમ્પ્યુટેશનલ સમસ્યાઓનો એક વર્ગ છે જેમાં ઇનપુટ એ પ્રવાહ નેટવર્ક છે (તેની ધાર પર આંકડાકીય ક્ષમતાઓ સાથેનો આલેખ), અને ધ્યેય એ છે કે દરેક ધાર પર પ્રવાહ, આંકડાકીય મૂલ્યોનું નિર્માણ કરવું કે જે ક્ષમતાની મર્યાદાઓને માન આપે છે અને જે ચોક્કસ નિયુક્ત ટર્મિનલ્સ સિવાય તમામ શિરોબિંદુઓ પર આઉટગોઇંગ પ્રવાહની બરાબર આવતા પ્રવાહ ધરાવે છે. નેટવર્ક પ્રવાહ સમસ્યાઓના ચોક્કસ પ્રકારોમાં નીચેનાનો સમાવેશ થાય છેઃ મહત્તમ પ્રવાહ સમસ્યા, જેમાં સ્રોત ટર્મિનલમાંથી અને સિંક ટર્મિનલમાં પ્રવાહની કુલ માત્રાને મહત્તમ કરવાનો ધ્યેય હોય છે લઘુત્તમ-ખર્ચ પ્રવાહ સમસ્યા, જેમાં ધારની કિંમત તેમજ ક્ષમતાઓ હોય છે અને ધ્યેય આપેલ પ્રવાહની માત્રા (અથવા મહત્તમ પ્રવાહ) પ્રાપ્ત કરવાનો હોય છે જેનો ઓછામાં ઓછો સંભવિત ખર્ચ હોય છે બહુ-વસ્તુ પ્રવાહ સમસ્યા, જેમાં વ્યક્તિએ વિવિધ ચીજવસ્તુઓ માટે બહુવિધ પ્રવાહોનું નિર્માણ કરવું આવશ્યક છે, જેમના કુલ પ્રવાહની માત્રા એકસાથે ક્ષમતાને માન આપે છે. અંદાજિત મહત્તમ-પ્રવાહ લઘુતમ-કટ પ્રમેયો આ પરિણામનું બહુ-કોમોડિટી પ્રવાહ સમસ્યાઓનું વિસ્તરણ પ્રદાન કરે છે. દિશાહીન પ્રવાહ નેટવર્કનું ગોમોરી-હુ વૃક્ષ અંતિમ શિરોબિંદુઓની વિવિધ જોડી વચ્ચેના તમામ લઘુતમ કાપોનું સંક્ષિપ્ત પ્રતિનિધિત્વ પ્રદાન કરે છે. પ્રવાહના નિર્માણ માટેના અલ્ગોરિધમ્સમાં ડિનિકનું અલ્ગોરિધમ, મહત્તમ પ્રવાહ માટે મજબૂત બહુપદી અલ્ગોરિધમ, એડમંડ્સ-કાર્પ અલ્ગોરિધમ, મહત્તમ પ્રવાહ માટે ઝડપી મજબૂત બહુપદી અલ્ગોરિધમ, ફોર્ડ-ફુલ્કરસન અલ્ગોરિધમ, મહત્તમ પ્રવાહ માટે લોભી અલ્ગોરિધમ જે સામાન્ય રીતે મજબૂત બહુપદી નથી, નેટવર્ક સિમ્પ્લેક્સ અલ્ગોરિધમ, રેખીય પ્રોગ્રામિંગ પર આધારિત એક પદ્ધતિ છે પરંતુ નેટવર્ક પ્રવાહ માટે વિશિષ્ટ છે. આલેખ અલ્ગોરિધમ્સ સંયુક્ત ઓપ્ટિમાઇઝેશન નિર્દેશિત આલેખ