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