يمكن تمثيل العديد من المشكلات في علوم الكمبيوتر من خلال رسم بياني يتكون من عُقد وروابط بينها. ومن الأمثلة على ذلك مشكلات تدفق الشبكة، والتي تتضمن نقل البضائع أو المواد عبر شبكة، مثل نظام السكك الحديدية.
يمكنك تمثيل تدفق الشبكة من خلال رسم بياني تكون عُقده مدنًا وأقواسها هي خطوط السكك الحديدية بينها. (تُسمى التدفقات لأن خصائصها مشابهة لخصائص المياه التي تتدفق من خلال شبكة من الأنابيب).
يتمثل القيد الرئيسي في تدفقات الشبكة في أن لكل قوس سعة — وهو أقصى مبلغ يمكن نقله عبر القوس في فترة زمنية ثابتة.
تكمن مشكلة الحد الأقصى في التدفق في تحديد الحد الأقصى للمبلغ الإجمالي الذي يمكن نقله عبر جميع الأقواس في الشبكة، وذلك وفقًا لقيود السعة.
كان أول عالم يدرس هذه المشكلة هو عالم الرياضيات الروسي "آي إن تولستوي" في ثلاثينيات القرن العشرين. توضح الخريطة أدناه شبكة السكك الحديدية الفعلية التي أراد العثور على أقصى تدفق لها.
توفر "أدوات OR" عدة أدوات حل لمشكلات تدفق الشبكة في مكتبات الرسم البياني التابعة لها.
تقدم الأقسام التالية أمثلة لمشكلات تدفق الشبكة وتوضّح كيفية حلها: