مسألة التدفق الأقصى

في إطار نظرية التحسين، تُعنى مسائل التدفق الأقصى بإيجاد تدفق ممكن عبر شبكة تدفق يحقق أعلى معدل تدفق ممكن.

.

يمكن اعتبار مشكلة التدفق الأقصى حالة خاصة من مسائل تدفق الشبكات الأكثر شمولية، مثل مشكلة الدورة الدموية .. وتنص نظرية الحد الأقصى للتدفق والحد الأدنى للقطع على أن القيمة القصوى للتدفق من المصدرs إلى المصرف t (يُشار إليها بتدفق st) تعادل الحد الأدنى لسعة أي قطع يفصل s عن t (يُشار إليه بقطع st) في الشبكة..

 تاريخ 
طُرحت مشكلة التدفق الأقصى للمرة الأولى في عام 1954 على يد TE Harris و FS Ross، وذلك كنموذج مبسط لتدفق حركة المرور على شبكة السكك الحديدية السوفيتية .

1955، ابتكر ليستر ر. فورد الابن وديلبرت ر. فولكرسون أول خوارزمية معروفة، وهي خوارزمية فورد-فولكرسون . في ورقتهم البحثية لعام 1955، كتب فورد وفولكرسون أن مشكلة هاريس وروس صيغت على النحو التالي تخيل شبكة سكك حديدية تصل بين مدينتين مرورًا بعدة مدن أخرى، حيث يمثل رقم محدد لسعة كل وصلة في هذه الشبكة. وبافتراض استقرار الظروف التشغيلية، المطلوب هو إيجاد أقصى قدر من التدفق (مثل عدد القطارات أو حجم البضائع) يمكن نقله من مدينة معينة إلى مدينة أخرى. في كتابهما الذي يحمل عنوان "التدفقات في الشبكات" والذي نُشر عام 1962، كتب فورد وفولكرسون ما يلي:عُرضت هذه الفكرة على المؤلفين في ربيع عام 1955 من قِبل تي إي هاريس، الذي قام، بالاشتراك مع الجنرال المتقاعد إف إس روس، بصياغة نموذج مبسط لتدفق حركة السكك الحديدية، وحدد هذه المشكلة تحديدًا باعتبارها القضية الأساسية التي يطرحها النموذج [11].حيث يشير [11] إلى التقرير السري لعام 1955 " تعتمد طريقة تقييم قدرات شبكات السكك الحديدية على قياس وتحليل أقصى إمكانية لاستيعاب حركة القطارات مع الحفاظ على مستوى خدمة مقبول، وذلك بفحص أنواع القدرة (نظرية، عملية، مستخدمة، متبقية) والعوامل المؤثرة (البنية التحتية، التشغيل، الأداء)، وتطبيق أدوات تحليلية ومحاكاة لدعم التخطيط والتحسين واتخاذ القرارات الاستراتيجية. "بقلم هاريس وروس  (انظر  ص. 5).

على مدار السنوات، تم اكتشاف العديد من الحلول المحسنة لمسألة التدفق الأقصى، وأهمها خوارزمية أقصر مسار متزايد التي توصل إليها كل من إدموندز وكارب ودينيتز بشكل مستقل، بالإضافة إلى خوارزمية التدفق الحاجز التي ابتكرها دينيتز.

، تم اكتشاف العديد من الحلول المحسنة لمسألة التدفق الأقصى، وأهمها خوارزمية أقصر مسار متزايد التي توصل إليها كل من إدموندز وكارب ودينيتز بشكل مستقل، بالإضافة إلى خوارزمية التدفق الحاجز التي ابتكرها دينيتز.؛ وخوارزمية الدفع وإعادة التسمية لجولدبيرج وتارجان ؛ وخوارزمية التدفق الحاجز الثنائي لجولدبيرج وراو. تجد خوارزميات شيرمان  وكيلنر ولي وأوريكيا وسيدفورد،  على التوالي، تدفقًا أقصى مثاليًا تقريبًا ولكنها تعمل فقط في الرسوم البيانية غير الموجهة.

في عام 2013، نشر جيمس ب. أورلين ورقة بحثية تصف خوارزمية تعمل في زمن قدره .

في عام 2022، نشر لي تشين، وراسموس كينج، ويانج بي ليو، وريتشارد بينج، وماكسيميليان بروبست جوتنبرج، وسوشانت ساشديفا خوارزمية تعمل في زمن شبه خطي قدره  لحل مشكلة التدفق ذات التكلفة الدنيا ، والتي تُعد مشكلة التدفق الأقصى حالة خاصة منها. وبالنسبة لمشكلة أقصر مسار من مصدر واحد (SSSP) ذات الأوزان السالبة، وهي حالة خاصة أخرى من مشكلة التدفق ذات التكلفة الدنيا، فقد تم الإعلان عن خوارزمية تعمل في زمن يقارب الزمن الخطي. وقد حظيت كلتا الخوارزميتين بتقدير أفضل ورقتين بحثيتين في ندوة أساسيات علوم الكمبيوتر لعام 2022.

 تعريف 
تصغير|شبكة تدفق، مع مصدر s ومصرف t . الأرقام بجوار الحواف هي السعات.
أولاً نقوم بإنشاء بعض التدوينات:

 يترك  كن شبكة مع  كونها المصدر والمصرف  على التوالى.
 لو  هي دالة على حواف  ثم قيمتها على  يتم الإشارة إليه بواسطة  أو 

تعريف: سعة الحافة هي الحد الأعلى لكمية التدفق التي يمكن أن تعبر من خلال تلك الحافة. ويُعبر عنها رياضيًا بدالة c تربط كل حافة E بقيمة حقيقية موجبة أو صفرية من المجموعة R ()

تعريف. التدفق عبارة عن خريطة  الذي يلبي الشروط التالية:

 قيد القدرة . لا يمكن لتدفق الحافة أن يتجاوز سعتها، بمعنى آخر:  للجميع 
 حفظ التدفقات. يجب أن يساوي مجموع التدفقات الداخلة إلى عقدة ما مجموع التدفقات الخارجة من تلك العقدة، باستثناء المصدر والمصرف. أو:



ملاحظة . التدفقات متماثلة بشكل غير متساوٍ:  للجميع 

تعريف: قيمة التدفق هي إجمالي كمية التدفق الصافي التي تنتقل من المصدر إلى المصب. وبالنسبة لتدفق معين ، تُعطى قيمته بالعلاقة التالية:



تعريف: تُعنى مشكلة التدفق الأقصى بإيجاد طريقة لتوجيه أكبر قدر ممكن من التدفق من نقطة المصدر إلى نقطة المصب في الشبكة. بعبارة أخرى، الهدف هو تحديد التدفق الأمثل () الذي يحقق أعلى قيمة ممكنة.

تجدر الإشارة إلى أنه قد توجد حلول متعددة لمشكلة التدفق الأقصى. وعندما يُسمح لقيم التدفق بأن تكون أعدادًا حقيقية أو حتى نسبية اختيارية (بدلاً من اقتصارها على الأعداد الصحيحة)، فإننا إما أن نجد حلاً أقصى واحدًا بالضبط، أو عددًا لا نهائيًا من الحلول. ويرجع ذلك إلى وجود عدد لا نهائي من التركيبات الخطية للتدفقات القصوى الأساسية. بمعنى آخر، إذا كان التدفق الأقصى الأول يرسل x وحدة تدفق عبر الحافة u، وكان تدفق أقصى آخر يرسل y وحدة تدفق عبر نفس الحافة u (حيث y > x)، فإنه لكل قيمة Δ تقع في النطاق ، يمكننا إرسال x + Δ وحدة عبر الحافة u وتعديل التدفق على الحواف الأخرى وفقًا لذلك، لنحصل على تدفق أقصى آخر. إذا كانت قيم التدفق يمكن أن تأخذ أي قيمة حقيقية أو نسبية، فسيكون هناك عدد لا نهائي من قيم Δ الممكنة لكل زوج من القيم x و y.

 الخوارزميات 
الجدول التالي يسرد الخوارزميات المستخدمة لحل مشكلة التدفق الأقصى. في هذا الجدول، يمثل ∣V∣ عدد الرؤوس ويمثل ∣E∣ عدد الحواف في الشبكة. أما القيمة U فتشير إلى أكبر سعة حافة بعد تحويل جميع السعات إلى قيم صحيحة (إذا كانت الشبكة تتضمن سعات غير نسبية، فقد تكون قيمة U لانهائية).

لمزيد من الخوارزميات، راجع  .

 نظرية التدفق التكاملي 
تنص نظرية التدفق التكاملي على أن

 إذا كان لكل حافة في شبكة التدفق سعة متكاملة، فسيكون هناك تدفق أقصى متكامل.

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

 طلب 

 مشكلة التدفق الأقصى متعدد المصادر ومتعدد الأحواض 
يسار|تصغير| الشكل 4.1.1. تحويل مشكلة التدفق الأقصى متعدد المصادر ومتعدد المصارف إلى مشكلة التدفق الأقصى أحادي المصدر ومصرف واحد
عند التعامل مع شبكة  تحتوي على مجموعة من المصادر  ومجموعة من المصارف  بدلاً من مصدر واحد ومصرف واحد فقط، يصبح الهدف هو إيجاد الحد الأقصى للتدفق عبر N. يمكننا تحويل هذه المشكلة متعددة المصادر والمصارف إلى مشكلة تدفق أقصى تقليدية عن طريق إضافة مصدر موحد يرتبط بكل رأس في S، ومصب موحد يرتبط بكل رأس في T (يُعرفان أيضًا بالمصدر الفائق والمصب الفائق) مع تخصيص سعة لانهائية لكل حافة من هذه الروابط الجديدة (انظر الشكل 4.1.1).

 مطابقة ثنائية الأجزاء لأقصى عدد أساسي 
يسار|تصغير| الشكل 4.3.1. تحويل مشكلة مطابقة ثنائي الجزء الأقصى إلى مشكلة التدفق الأقصى
بالنظر إلى الرسم البياني ثنائي الأجزاء ، فإن الهدف هو إيجاد الحد الأقصى لعدد العناصر المتطابقة في G، أي المطابقة التي تضم أكبر عدد ممكن من الحواف. يمكن تحويل هذه المشكلة إلى مشكلة تدفق أقصى عن طريق إنشاء شبكة ، حيث ان :

  يحتوي على الحواف في  موجه من  ل  .
  لكل واحد  و  لكل واحد  .
  لكل واحد  (انظر الشكل 4.3.1).

عندئذٍ، تكون قيمة التدفق الأقصى في الشبكة N مساوية لحجم المطابقة القصوى في الرسم البياني G. ويمكن تحديد المطابقة ذات أكبر عدد من الحواف عن طريق اختيار تلك الحواف التي يحمل تدفقها قيمة 1 في التدفق الأقصى الذي تكون قيمه عددًا صحيحًا.

 الحد الأدنى لتغطية المسار في الرسم البياني اللادوري الموجه 
بالنظر إلى الرسم البياني غير الدوري الموجه ، فإن الهدف هو إيجاد الحد الأدنى لعدد المسارات المنفصلة عن الرؤوس التي تغطي جميع الرؤوس في V. يمكننا إنشاء رسم بياني ثنائي الأجزاء  ,  من G، حيث:



  .

وبالتالي، يمكننا أن نوضح أن الرسم البياني G' يمتلك مطابقة M بحجم m إذا وفقط إذا كان الرسم البياني G يحتوي على غطاء مسار منفصل من حيث الرؤوس C يتكون من m حافة و  مسارًا، حيث n هو عدد الرؤوس في G. ونتيجة لذلك، يمكن حل المشكلة عن طريق إيجاد الحد الأقصى لحجم المطابقة في G' بدلاً من G.

لنفترض أننا توصلنا إلى تطابق M في G'، ونقوم بإنشاء الغطاء C بناءً عليه. من البديهي أنه إذا كان الرأسان  و متطابقين في M، فإن الحافة (u, v) ستكون موجودة في C. من الواضح أن عدد الحواف في C سيكون m. لتوضيح أن C منفصل من حيث الرؤوس، تأمل ما يلي:

 كل رأس  في  يمكن أن تكون غير متطابقة في  ، وفي هذه الحالة لا توجد حواف متبقية  في  ؛ أو يمكن مطابقتها ، وفي هذه الحالة يكون هناك حافة واحدة فقط متبقية  في  . في كلتا الحالتين، لا يترك أكثر من حافة واحدة أي رأس  في  .
 وبالمثل لكل رأس  في  - إذا تم التطابق، هناك حافة واردة واحدة في  في  ؛ خلاف ذلك  ليس له حواف واردة في  .

ونتيجة لذلك، لا يوجد أي رأس في C لديه حافتان واردتان أو حافتان صادرتان، مما يعني أن جميع المسارات المكونة للغطاء C منفصلة عن بعضها البعض من حيث الرؤوس.

لإثبات أن الغطاء C له حجم ، نبدأ بغطاء فارغ ونقوم ببنائه تدريجيًا. لإضافة رأس u إلى الغطاء، لدينا خياران: إما إضافته إلى مسار موجود، أو إنشاء مسار جديد بطول صفر يبدأ من هذا الرأس. ينطبق الخيار الأول عندما توجد حافة  ويبدأ أحد المسارات في الغطاء عند v، أو عندما توجد حافة  وينتهي أحد المسارات عند v. أما الخيار الثاني (إنشاء مسار جديد) فهو ممكن دائمًا. في الحالة الأولى (إضافة إلى مسار موجود)، يزداد العدد الكلي للحواف في الغطاء بمقدار 1 بينما يظل عدد المسارات ثابتًا؛ وفي الحالة الثانية (إنشاء مسار جديد)، يزداد عدد المسارات بمقدار 1 بينما يظل عدد الحواف ثابتًا. من الواضح الآن أنه بعد تغطية جميع n رؤوس الرسم البياني G، سيكون مجموع عدد المسارات والحواف في الغطاء مساويًا لـ n. لذلك، إذا كان عدد الحواف في الغطاء هو m، فإن عدد المسارات سيكون .

 الحد الأقصى للتدفق مع قدرات القمة 
يسار|تصغير| الشكل 4.4.1. تحويل مشكلة التدفق الأقصى مع قيود سعة الرؤوس إلى مشكلة التدفق الأقصى الأصلية عن طريق تقسيم العقدة
لنفترض أن لدينا شبكة . بالإضافة إلى سعة كل حافة، نفترض أيضًا وجود سعة لكل عقدة، أي دالة تعيين ، بحيث يجب أن يفي التدفق  ليس فقط بقيد السعة التقليدي وقانون حفظ التدفق، بل أيضًا بقيد سعة الرأس (أو العقدة).



بعبارة أخرى، يجب ألا تتجاوز كمية التدفق العابر لأي رأس في الشبكة سعته المحددة. ولإيجاد الحد الأقصى للتدفق عبر الشبكة N، يمكننا تحويل هذه المسألة إلى مشكلة تدفق أقصى بالمعنى التقليدي من خلال توسيع الشبكة N.

 أولا، كل  يتم استبداله بـ  و  ، أين  متصل بواسطة حواف متوجهة إلى  و  متصل بالحواف الخارجة من  ،
 ثانيا بتعيين السعة  إلى الحافة المتصلة  و  (انظر الشكل 4.4.1).

في هذا التمثيل الموسع للشبكة، يُلغى القيد المفروض على سعة الرأس، مما يتيح لنا حل المشكلة باستخدام تقنيات التدفق الأقصى التقليدية.

 الحد الأقصى لعدد المسارات من s إلى t 
بالنظر إلى رسم بياني موجه  ورأسين محددين s و t، فإن الهدف هو إيجاد الحد الأقصى لعدد المسارات المنفصلة من s إلى t. لهذه المسألة عدة صور:

1. أولاً، يجب أن تكون المسارات منفصلة من حيث الحواف. يمكن تحويل هذه المشكلة إلى مشكلة تدفق أقصى عن طريق إنشاء شبكة  من الرسم البياني G، مع اعتبار s و t هما المصدر والمصب في N على التوالي، وتعيين سعة قدرها 1 لكل حافة. في هذه الشبكة، يكون الحد الأقصى للتدفق هو k إذا كان هناك k مسارًا منفصلاً من حيث الحواف.

2. ثانيًا، يجب أن تكون المسارات مستقلة، أي لا تشترك في أي رؤوس فيما بينها (باستثناء الرأسين s و t). يمكننا بناء شبكة  من الرسم البياني G مع إضافة سعات للرؤوس، حيث تكون سعة كل رأس وكل حافة مساوية لـ 1. في هذه الحالة، تكون قيمة التدفق الأقصى مساوية لأكبر عدد من المسارات المستقلة من s إلى t.

3. بالإضافة إلى اشتراط فصل المسارات من حيث الحواف و/أو الرؤوس، قد يكون للمسارات أيضًا قيد على طولها: حيث نحسب فقط المسارات التي يكون طولها k بالضبط، أو على الأكثر k. معظم المتغيرات لهذه المشكلة تصنف ضمن المسائل NP-كاملة، باستثناء الحالات التي تكون فيها قيمة k صغيرة.

 مشكلة الإغلاق 

في الرسم البياني الموجه، الإغلاق هو مجموعة من الرؤوس C بحيث لا توجد أي حافة تبدأ من رأس في C وتنتهي في رأس خارج C. ومشكلة الإغلاق هي مهمة إيجاد إغلاق ذي أقصى وزن أو أدنى وزن في رسم بياني موجه تكون رؤوسه مُوزنة. يمكن حل هذه المشكلة في زمن متعدد الحدود عن طريق اختزالها إلى مشكلة التدفق الأقصى.

 تطبيقات العالم الحقيقي 

 إقصاء البيسبول 
تصغير|إنشاء تدفق الشبكة لمشكلة إقصاء البيسبول
في سياق مشكلة الإقصاء في دوري لعبة البيسبول، يتنافس n فريقًا. في مرحلة معينة من الموسم، يمثل wᵢ عدد مرات فوز الفريق i، و rᵢ عدد المباريات المتبقية للفريق i، بينما يمثل rᵢⱼ عدد المباريات المتبقية بين الفريقين i و j. يُعتبر الفريق مُقصًى إذا لم يعد لديه أي فرصة رياضية لإنهاء الموسم في الصدارة. وتتمثل مهمة مشكلة إقصاء البيسبول في تحديد الفرق التي تم إقصاؤها عند أي نقطة خلال الموسم. اقترح شوارتز  طريقة لتبسيط هذه المشكلة وتحويلها إلى مشكلة تدفق أقصى في شبكة. تتضمن هذه الطريقة إنشاء شبكة خاصة لتحديد ما إذا كان سيتم استبعاد فريق معين k.

لنفترض أن G = (V, E) هي شبكة، حيث يمثل s المصدر و t المصب. نضيف عقدة "لعبة ij" لكل مباراة بين الفريقين i و j (حيث i < j) إلى V، ونربط s بكل عقدة لعبة {i, j} بحافة ذات سعة rᵢⱼ تمثل عدد مرات اللعب بينهما. نضيف أيضًا عقدة "فريق" لكل فريق مشارك، ونربط كل عقدة لعبة {i, j} بعقدتي الفريق i و j لضمان فوز أحدهما في كل مباراة. لا يلزم تقييد قيمة التدفق على هذه الحواف الرابطة بين عقد اللعبة وعقد الفريق. أخيرًا، ننشئ حوافًا من عقدة الفريق i إلى عقدة المصب t ونضبط سعتها على  لمنع الفريق i من الفوز بأكثر من  مرة. ليكن S مجموعة جميع الفرق المشاركة في الدوري، وليكن...

  .

في هذه الطريقة، يُدعى أن الطاقم k لا يُستبعد من الجدول الزمني إذا وفقط إذا وُجدت قيمة تدفق بحجم r(S - {k}) في الشبكة G. وقد تم إثبات أن قيمة هذا التدفق، كما ورد في المقالة المذكورة، هي قيمة التدفق الأقصى من المصدر s إلى المصب t.

 جدولة خطوط الطيران 
في قطاع الطيران، تُعد جدولة أطقم الطيران من التحديات الرئيسية. ويمكن اعتبار مشكلة جدولة الخطوط الجوية تطبيقًا لمفهوم تدفق الشبكة الأقصى الموسع. تتضمن مدخلات هذه المشكلة مجموعة من الرحلات الجوية F، مع تفاصيل حول مكان وزمان إقلاع ووصول كل رحلة. وفي إحدى صيغ جدولة الخطوط الجوية، يتمثل الهدف في إنشاء جدول زمني عملي لا يتطلب أكثر من ألف طاقم.

لحل هذه المسألة، يُستخدم نوع خاص من مشكلة الدورة الدموية يُعرف بالدورة المحدودة، وهو تعميم لمشاكل تدفق الشبكة يضيف قيدًا إضافيًا يتمثل في وجود حد أدنى لقيم التدفق على الحواف.

لنفترض أن G = (V, E) هي شبكة، حيث يمثل s و t عقدتي المصدر والمصب الرئيسيتين في V. لكل رحلة i، ذات مصدر ووجهة محددتين، نضيف عقدتين جديدتين إلى V: العقدة sᵢ لتمثيل مصدر الرحلة i، والعقدة dᵢ لتمثيل وجهة الرحلة i. بالإضافة إلى ذلك، نضيف الحواف التالية إلى E:

 حافة بسعة [0، 1] بين s وكل s i .
 حافة بسعة [0، 1] بين كل d i و t .
 حافة بسعة [1، 1] بين كل زوج من s i و d i .
 حافة بسعة [0، 1] بين كل d i و s j ، إذا كان من الممكن الوصول إلى المصدر s j في فترة زمنية معقولة وتكلفة من وجهة الرحلة i .
 حافة بسعة [0، ∞ ] بين s و t .

في الطريقة المذكورة سابقًا، تم إثبات والتأكيد على أن إيجاد قيمة تدفق k في الشبكة G بين المصدر s والمصب t يعادل إيجاد جدول زمني قابل للتطبيق لمجموعة الرحلات الجوية F باستخدام k طاقم كحد أقصى. .

توجد صيغة أخرى لمشكلة جدولة الخطوط الجوية تتمثل في إيجاد الحد الأدنى لعدد أفراد الطاقم اللازمين لتنفيذ جميع الرحلات الجوية المقررة. لحل هذه المشكلة، يُنشأ رسم بياني ثنائي الأجزاء G' = (A ∪ B, E)، حيث تُمثل كل رحلة جوية بنسخة في المجموعة A ونسخة أخرى في المجموعة B. إذا كان من الممكن لنفس الطاقم القيام بالرحلة j بعد الرحلة i، فإنه يتم إنشاء وصلة بين i∈A و j∈B. يؤدي إيجاد تطابق في G' إلى إنشاء جدول زمني لمجموعة من الرحلات F. ومن الواضح أن إيجاد التطابق الثنائي الأقصى (من حيث عدد الحواف) في هذا الرسم البياني ينتج عنه جدول زمني لشركة الطيران بأقل عدد ممكن من أفراد الطاقم. وكما ذُكر في قسم التطبيقات من هذه المقالة، فإن إيجاد التطابق الثنائي ذي العدد الأساسي الأقصى هو تطبيق مباشر لمشكلة التدفق الأقصى.

 مشكلة التداول والطلب 
تخيل سيناريو يتضمن عددًا من المصانع التي تنتج سلعًا وعددًا من القرى التي تحتاج إلى هذه السلع. تربط هذه المدن شبكة من الطرق، ولكل طريق قدرة استيعابية محددة (c) تحدد أقصى كمية من البضائع يمكن نقلها عبره. السؤال المطروح هو: هل يوجد نظام توزيع (تداول) قادر على تلبية طلبات جميع القرى؟ يمكن تحويل هذه المشكلة إلى مسألة تدفق أقصى لحلها.

 أضف عقدة مصدر  وأضف حوافًا منها إلى كل عقدة مصنع  بسعة  حيث  هو معدل إنتاج المصنع  .
 أضف عقدة الحوض  وأضف الحواف من جميع القرى  إلى  بسعة  حيث  هو معدل الطلب للقرية  .

ليكن G = (V, E) هذه الشبكة المُنشأة حديثًا. عندئذٍ، يكون هناك تداول يلبي الطلب إذا وفقط إذا تحققت الشروط التالية:

  .

في سياق التبادل التجاري، يمكن أن يوفر حل مشكلة التدفق الأقصى إجابة حول كمية البضائع المثلى التي يجب نقلها عبر كل طريق لتلبية الطلبات المختلفة.

من الممكن توسيع نطاق هذه المشكلة عن طريق فرض حد أدنى لقيمة التدفق على بعض الحواف في الشبكة. .

 تقسيم الصورة 
بديل=|يمين|تصغير|110x110بك| الصورة المصدرية بالحجم 8×8.
تصغير|شبكة تم بناؤها من الخريطة النقطية. المصدر على اليسار، والمغسلة على اليمين. كلما كانت الحافة داكنة، كلما كانت قدرتها أكبر. a i مرتفع عندما يكون البكسل أخضر، b i عندما لا يكون البكسل أخضر. جميع العقوبات p ij متساوية.
في كتابهما، يقدم كلاينبيرج وتاردوس خوارزمية لمعالجة مشكلة تقسيم الصور. تحديدًا، يقترحون خوارزمية لتحديد مناطق الخلفية والمقدمة في الصورة. وبشكل أكثر دقة، تستقبل الخوارزمية خريطة من البيانات الثنائية (بتات) كمدخل، ويتم تمثيل هذه البيانات على النحو التالي: aᵢ ≥ 0 يمثل احتمالية انتماء البكسل i إلى منطقة المقدمة، و bᵢ ≥ 0 يمثل احتمالية انتماء البكسل i إلى منطقة الخلفية، بينما تمثل pᵢⱼ قيمة العقوبة المترتبة على وضع بكسلين متجاورين i و j في منطقتين مختلفتين (أحدهما في المقدمة والآخر في الخلفية). الهدف من الخوارزمية هو إيجاد تقسيم (A, B) لمجموعة البكسلات يحقق أقصى قيمة للمقدار التالي:



في الواقع، بالنسبة لكل بكسل في المنطقة A (التي نعتبرها المقدمة)، نحصل على قيمة aᵢ. وبالمثل، بالنسبة لجميع البكسلات في المنطقة B (التي نعتبرها الخلفية)، نحصل على قيمة bᵢ. أما على الحدود بين أي بكسلين متجاورين i و j، فإننا نخسر قيمة pᵢⱼ. وهذا يعادل تقليل الكمية التالية:



لأن
تصغير|الحد الأدنى للقطع المعروض على الشبكة (المثلثات مقابل الدوائر).
الآن، نشرع في إنشاء شبكة تكون عقدها هي البكسلات، بالإضافة إلى عقدتي المصدر والمصب، كما هو موضح في الشكل على اليمين. ننشئ حافة موجهة من المصدر إلى البكسل i بوزن قدره aᵢ. وبالمثل، ننشئ حافة موجهة من البكسل i إلى المصب بوزن قدره bᵢ. كما ننشئ حافة غير موجهة بين أي بكسلين متجاورين i و j بوزن قدره pᵢⱼ. الآن، يبقى علينا حساب الحد الأدنى للقطع في هذه الشبكة (أو ما يكافئه من تدفق أقصى). ويوضح الشكل الأخير الحد الأدنى لهذا القطع.

 الامتدادات 
1. في مشكلة التدفق بأقل تكلفة ، تُضاف إلى كل حافة (u, v) معامل تكلفة uv بالإضافة إلى سعتها. وإذا كان التدفق عبر هذه الحافة هو f uv، فإن التكلفة الإجمالية تُحسب بضرب uv f uv في f uv. المطلوب هو إيجاد تدفق بحجم معين d يحقق أقل تكلفة ممكنة. وفي معظم صور هذه المسألة، يمكن أن تكون معاملات التكلفة إما موجبة أو سالبة. توجد العديد من الخوارزميات التي تعمل في زمن متعدد الحدود لحل هذه المشكلة.

2. يمكن تعقيد مشكلة التدفق الأقصى بإضافة قيود منفصلة. ينص القيد المنفصل السلبي على أنه لا يمكن لزوج معين من الحواف أن يحمل تدفقًا غير صفري في نفس الوقت. أما القيد المنفصل الإيجابي فيشترط أنه في زوج معين من الحواف، يجب أن يكون لدى واحدة على الأقل تدفق غير صفري. عند وجود قيود سلبية، تصبح المشكلة صعبة للغاية حتى في الشبكات البسيطة. أما مع القيود الإيجابية، فتكون المشكلة قابلة للحل في زمن متعدد الحدود إذا سُمح بقيم تدفق كسرية، ولكنها قد تصبح من المسائل NP-صعبة عندما يجب أن تكون قيم التدفق أعدادًا صحيحة.

 قراءة إضافية 





تصنيف:استمثال رياضي