التدفق الفرعي

في نظرية التحسين التوافقي ، يُعدّ التدفق شبه المعياري فئة عامة من مسائل التحسين، تشمل كحالات خاصة مسألة التدفق ذي التكلفة الدنيا ، وتقاطع الماترويد ، ومسألة حساب التدفق الثنائي ذي الوزن الأدنى في رسم بياني موجه مُثقّل . وقد صاغها في الأصل جاك إدموندز وريك جايلز، ^{[ 1 ]} ويمكن حلها في وقت متعدد الحدود . ^{[ 2 ] [ 3 ] [ 4 ]}

في مسألة التدفق الكلاسيكية ذات التكلفة الدنيا، يكون المدخل عبارة عن شبكة تدفق ذات سعات محددة تحدد الحدين الأدنى والأعلى لكمية التدفق لكل حافة، بالإضافة إلى تكاليف وحدة التدفق على طول كل حافة. ​​والهدف هو إيجاد نظام لكميات التدفق التي تفي بالسعات على كل حافة، وتتوافق مع قانون كيرشوف الذي ينص على أن إجمالي كمية التدفق الداخل إلى كل رأس يساوي إجمالي كمية التدفق الخارج منه، وأن تكون ذات أقل تكلفة إجمالية. في التدفق شبه المعياري أيضًا، تُعطى دالة مجموعة شبه معيارية على مجموعات رؤوس الرسم البياني. وبدلًا من التقيد بقانون كيرشوف، يُشترط، لكل مجموعة رؤوس، ألا يتجاوز التدفق الزائد (الدالة التي تربط المجموعة بالفرق بين التدفق الداخل والتدفق الخارج منها) القيمة التي تحددها الدالة شبه المعيارية. ^{[ 4 ]}