কম্পিউটার বিজ্ঞানের অনেক সমস্যা নোড এবং তাদের মধ্যে লিঙ্ক সমন্বিত একটি গ্রাফ দ্বারা প্রতিনিধিত্ব করা যেতে পারে। উদাহরণ হল নেটওয়ার্ক প্রবাহের সমস্যা, যা একটি নেটওয়ার্ক জুড়ে পণ্য বা উপাদান পরিবহনের সাথে জড়িত, যেমন একটি রেল ব্যবস্থা।
আপনি একটি গ্রাফ দ্বারা একটি নেটওয়ার্ক প্রবাহ উপস্থাপন করতে পারেন যার নোডগুলি শহর এবং যার আর্কগুলি তাদের মধ্যে রেল লাইন। ( এগুলিকে প্রবাহ বলা হয় কারণ তাদের বৈশিষ্ট্যগুলি পাইপের নেটওয়ার্কের মধ্য দিয়ে প্রবাহিত জলের মতো।)
নেটওয়ার্ক প্রবাহের একটি প্রধান সীমাবদ্ধতা হল প্রতিটি চাপের একটি ক্ষমতা থাকে — সর্বোচ্চ পরিমাণ যা একটি নির্দিষ্ট সময়ের মধ্যে চাপের মধ্যে পরিবহন করা যেতে পারে।
সর্বাধিক প্রবাহের সমস্যা হল সর্বাধিক মোট পরিমাণ নির্ধারণ করা যা নেটওয়ার্কের সমস্ত আর্ক জুড়ে পরিবহন করা যেতে পারে, ক্ষমতার সীমাবদ্ধতা সাপেক্ষে।
এই সমস্যা অধ্যয়নকারী প্রথম ব্যক্তি ছিলেন রাশিয়ান গণিতবিদ এএন টলস্টয়, 1930 এর দশকে। নীচের মানচিত্রটি প্রকৃত রেলওয়ে নেটওয়ার্ক দেখায় যার জন্য তিনি সর্বাধিক প্রবাহ খুঁজে পেতে চেয়েছিলেন।
OR-Tools এর গ্রাফ লাইব্রেরিতে নেটওয়ার্ক প্রবাহের সমস্যার জন্য বেশ কয়েকটি সমাধান প্রদান করে।
নিম্নলিখিত বিভাগগুলি নেটওয়ার্ক প্রবাহ সমস্যার উদাহরণ উপস্থাপন করে এবং কীভাবে সেগুলি সমাধান করতে হয় তা দেখায়: