Network flow problem
ஒருங்கிணைந்த உகப்பாக்கத்தில், நெட்வொர்க் ஓட்ட சிக்கல்கள் என்பது கணக்கீட்டு சிக்கல்களின் ஒரு வகுப்பாகும், இதில் உள்ளீடு ஒரு ஓட்ட நெட்வொர்க் (அதன் விளிம்புகளில் எண் திறன்களைக் கொண்ட ஒரு வரைபடம்), மேலும் ஒரு ஓட்டத்தை உருவாக்குவதே குறிக்கோள், ஒவ்வொரு விளிம்பிலும் எண் மதிப்புகள் திறன் கட்டுப்பாடுகளை மதிக்கின்றன மற்றும் சில நியமிக்கப்பட்ட முனையங்களைத் தவிர அனைத்து செங்குத்துகளிலும் வெளிச்செல்லும் ஓட்டத்திற்கு சமமான உள்வரும் ஓட்டத்தைக் கொண்டுள்ளன. நெட்வொர்க் ஃப்லோ சிக்கல்களின் குறிப்பிட்ட வகைகள் பின்வருமாறுஃ அதிகபட்ச ஃப்லோ சிக்கல், இதில் மூல முனையங்களிலிருந்தும் சிங்க் முனையங்களிலிருந்தும் வெளியேறும் மொத்த ஓட்டத்தின் அளவை அதிகரிப்பதே குறிக்கோள் குறைந்தபட்ச-செலவு ஃப்லோ சிக்கல், இதில் விளிம்புகள் செலவுகளையும் திறன்களையும் கொண்டுள்ளன மற்றும் இலக்கு கொடுக்கப்பட்ட அளவு ஃப்லோவை (அல்லது அதிகபட்ச ஃப்லோவை) அடைவதே குறைந்தபட்ச சாத்தியமான செலவைக் கொண்டுள்ளது மல்டி-கமாடிட்டி ஃப்லோ சிக்கல், இதில் ஒருவர் வெவ்வேறு பொருட்களுக்கான பல ஃப்லோக்களை உருவாக்க வேண்டும், அதன் மொத்த ஃப்லோ அளவு ஒன்றாக திறன்களை மதிக்கிறது எங்கும்-பூஜ்ஜிய ஃப்லோ, காம்பினடோரிக்குகளில் ஆய்வு செய்யப்படும் ஒரு வகை ஃப்லோ, இதில் ஃப்லோ அளவுகள் பூஜ்ஜியமற்ற மதிப்புகளின் வரையறுக்கப்பட்ட தொகுப்புக்கு மட்டுப்படுத்தப்பட்டுள்ளன அதிகபட்ச ஃப்லோ மின்-கட் தேற்றம் மதிப்புக்கு அதிகபட்ச ஃப்லோவின் மதிப்பை சமன் செய்கிறது. தோராயமான அதிகபட்ச-ஓட்ட குறைந்தபட்ச-வெட்டு கோட்பாடுகள் இந்த முடிவின் விரிவாக்கத்தை பல பொருட்கள் ஓட்ட சிக்கல்களுக்கு வழங்குகின்றன. திசைதிருப்பப்படாத ஓட்ட நெட்வொர்க்கின் கோமோரி-ஹூ மரம் வெவ்வேறு ஜோடி முனைய செங்குத்துகளுக்கு இடையிலான அனைத்து குறைந்தபட்ச வெட்டுக்களுக்கும் ஒரு சுருக்கமான பிரதிநிதித்துவத்தை வழங்குகிறது. பாய்வுகளை உருவாக்குவதற்கான வழிமுறைகளில் டினிக்கின் வழிமுறை, அதிகபட்ச ஓட்டத்திற்கான வலுவான பல்லுறுப்புக்கோவை வழிமுறை எட்மண்ட்ஸ்-கார்ப் வழிமுறை, அதிகபட்ச ஓட்டத்திற்கான வேகமான வலுவான பல்லுறுப்புக்கோவை வழிமுறை ஃபோர்டு-ஃபுல்கர்சன் வழிமுறை, பொதுவாக வலுவாக பல்லுறுப்புக்கோவை இல்லாத அதிகபட்ச ஓட்டத்திற்கான பேராசை வழிமுறை நெட்வொர்க் சிம்ப்ளக்ஸ் வழிமுறை, நேரியல் நிரலாக்கத்தை அடிப்படையாகக் கொண்ட ஒரு முறை, ஆனால் நெட்வொர்க் ஓட்டத்திற்கு நிபுணத்துவம் பெற்றது குறைந்தபட்ச செலவு ஓட்டத்திற்கான வழிமுறைக்கு வெளியே கிலோமீட்டர் புஷ்-ரீலேபிள் அதிகபட்ச ஓட்ட வழிமுறை, அதிகபட்ச ஓட்டத்திற்கான மிகவும் திறமையான அறியப்பட்ட நுட்பங்களில் ஒன்றாகும் இல்லையெனில் சிக்கலை மிகவும் வழக்கமான நேரியல் நிரலாக வடிவமைக்கலாம் அல்லது ஒத்ததாக உருவாக்கலாம் மற்றும் ஒரு பொது நோக்க உகப்பாக்கம் தீர்வைப் பயன்படுத்தி தீர்க்கலாம். வரைபட வழிமுறைகள் ஒருங்கிணைந்த உகப்பாக்கம் இயக்கப்படும் வரைபடங்கள்