مشكلة التدفق الأقصى

تتميز الخوارزمية ذات الوقت متعدد الحدود القوي بحدود زمنية متعددة الحدود تعتمد فقط على عدد المدخلات، ولا تعتمد على مقدار هذه الأعداد. هنا، المدخلات هي الرؤوس (المرقمة أدناه كـ${\displaystyle V}$) والحواف (مرقمة كما${\displaystyle E}$يتم تحديد تعقيد كل خوارزمية باستخدام ترميز Big O.

طريقة	سنة	تعقيد	وصف
خوارزمية إدموندز-كارب [ 17 ]	1969	${\displaystyle O(VE^{2})}$	تخصص من فورد-فولكرسون، إيجاد مسارات معززة باستخدام البحث بالعرض أولاً .
خوارزمية دينيك [ 18 ]	1970	${\displaystyle O(V^{2}E)}$(أوزان اعتباطية)${\displaystyle O(\min\{V^{2/3},E^{1/2}\}E)}$(الأوزان الوحدوية)	مراحل متكررة تُنشئ رسمًا بيانيًا فرعيًا "طبقيًا" من حواف الرسم البياني المتبقية التي تنتمي إلى أقصر المسارات، باستخدام البحث بالعرض أولًا ، ثم تجد تدفقًا مانعًا (تدفقًا أقصى في هذا الرسم البياني الطبقي) في وقت${\displaystyle O(VE)}$لكل طور. يزداد طول أقصر مسار في كل طور، لذا يوجد على الأكثر${\displaystyle V-1}$مراحل.
خوارزمية كارزانوف [ 19 ]	1974	${\displaystyle O(V^{3})}$	خوارزمية سابقة لخوارزمية الدفع وإعادة التسمية تستخدم التدفقات المسبقة (وظائف التدفق التي تسمح بوجود فائض عند الرؤوس) لإيجاد تدفق مانع في كل مرحلة من مراحل خوارزمية دينيك في الوقت${\displaystyle O(V^{2})}$لكل مرحلة. أول خوارزمية تدفق زمنية مكعبة.
خوارزمية تشيركاسكي [ 20 ]	1977	${\displaystyle O{\bigl (}V^{2}{\sqrt {E}}{\bigr )}}$	يجمع هذا الأسلوب بين طريقتي التدفق المُعطِّل لـ Dinic (داخل كتل طبقات BFS المتتالية) و Karzanov (لدمج الكتل). وهو أول حد زمني شبه مكعب قوي متعدد الحدود للرسوم البيانية المتفرقة. وظل الأفضل لبعض قيم${\displaystyle E}$حتى عام 1988.
مالهوترا، كومار، وماهيشواري [ 21 ]	1978	${\displaystyle O(V^{3})}$	لا يُعدّ هذا تحسينًا في التعقيد مقارنةً بخوارزمية كارزانوف، بل هو تبسيط لها. تجد هذه الخوارزمية التدفقات المعيقة من خلال البحث المتكرر عن "عقدة مرجعية" في الرسم البياني الطبقي، وعن تدفق يُشبع جميع حوافها الواردة أو الصادرة، وذلك في زمن يتناسب مع عدد العقد مضافًا إليه عدد الحواف المشبعة.
خوارزمية جليل [ 22 ]	1978	${\displaystyle O(V^{5/3}E^{2/3})}$	يقوم بتعديل خوارزمية تشيركاسكي عن طريق استبدال طريقة إيجاد التدفقات داخل كتل الطبقات المتتالية.
جليل ونعامد وشيلوخ [ 23 ] [ 24 ]	1978	${\displaystyle O{\bigl (}VE(\log V)^{2}{\bigr )}}$	يستخدم تقليص الشجرة في غابة بحث العرض أولاً للرسم البياني الطبقي لتسريع تدفقات الحظر. الأول من بين العديد${\displaystyle O(VE\operatorname {polylog} V)}$الخوارزميات، لا تزال أفضل الأسس متعددة الحدود لخوارزمية متعددة الحدود قوية.
حجب التدفق باستخدام أشجار الربط/القطع . [ 25 ]	1981	${\displaystyle O(VE\log V)}$	يقدم بنية بيانات شجرة الربط/القطع ويستخدمها لإيجاد مسارات معززة في الشبكات متعددة الطبقات في الوقت المستهلك اللوغاريتمي لكل مسار.
خوارزمية الدفع وإعادة التسمية مع أشجار الربط/القطع [ 26 ]	1986	${\displaystyle O\left(VE\log {\frac {V^{2}}{E}}\right)}$	تحافظ خوارزمية الدفع وإعادة التسمية على تدفق أولي، ودالة ارتفاع تُقدّر المسافة المتبقية إلى الوجهة. تُعدّل هذه الخوارزمية التدفق الأولي بدفع الفائض إلى رؤوس ذات ارتفاع أقل، وتزيد دالة الارتفاع عند الرؤوس التي لا تحتوي على حواف متبقية إلى ارتفاعات أقل، حتى يعود كل الفائض إلى المصدر. تسمح أشجار الربط/القطع بعمليات الدفع على طول المسارات بدلاً من حافة واحدة في كل مرة.
شيريان وهاجيروب [ 27 ]	1989	عشوائي،${\displaystyle O{\bigl (}VE+V^{2}(\log V)^{2}{\bigr )}}$باحتمالية عالية	إعادة تسمية الحواف على رسم بياني فرعي تتم إضافة حافة واحدة إليه في كل مرة، مع إعطاء الأولوية لعمليات الدفع ذات الكميات الزائدة العالية، باستخدام قوائم تجاور مُبدَّلة عشوائيًا.
ألون [ 28 ]	1989	${\displaystyle O(VE+V^{8/3}\log V)}$	إزالة العشوائية من شيريان وهاجيروب
شيريان، هاجيروب، ومهلهورن [ 29 ]	1990	${\displaystyle \displaystyle O\left({\frac {V^{3}}{\log V}}\right)}$	يستخدم ألون عملية إزالة العشوائية لـ Cheriyan و Hagerup مع أفكار تتعلق بطريقة الروس الأربعة لتسريع البحث عن الحواف التي تقلل الارتفاع والتي يمكن دفع الفائض عليها.
كينغ، راو، وتارجان [ 30 ]	1992	${\displaystyle O(VE+V^{2+\varepsilon })}$لأي${\displaystyle \varepsilon >0}$	إعادة صياغة أخرى لنموذج شيريان وهاجيروب. نسخة أولية من نموذج كينج، راو، وتارجان 1994 بحدود أضعف.
فيليبس وويستبروك [ 31 ]	1993	${\displaystyle O(VE\log _{E/V}V+V(\log V)^{2+\varepsilon })}$لأي${\displaystyle \varepsilon >0}$	تم تطويره من King و Rao و Tarjan 1992 باستخدام أفكار مماثلة.
كينغ، راو، وتارجان [ 32 ]	1994	${\displaystyle O\left(VE\log _{\frac {E}{V\log V}}V\right)}$	تم تطويرها من قبل فيليبس وويستبروك باستخدام أفكار مماثلة.
أورلين [ 9 ]	2013	${\displaystyle O(VE)}$	يطبق خوارزمية شبه متعددة الحدود لغولدبرغ وراو على شبكة مضغوطة، يتم صيانتها باستخدام هياكل بيانات للإغلاق الديناميكي المتعدي. يستغرق وقتًا${\displaystyle O{\bigr (}VE+E^{31/16}(\log V)^{2}{\bigr )}}$، وهو ما يتبسط إلى${\displaystyle O(VE)}$ل${\displaystyle E=O(V^{16/15-\varepsilon })}$بينما تتبسط الحدود السابقة إلى${\displaystyle O(VE)}$ل${\displaystyle E=\Omega (V^{1+\epsilon })}$.
أورلين وجونج [ 33 ]	2021	${\displaystyle \displaystyle O\left({\frac {VE\log V}{\log \log V+\log {\tfrac {E}{V}}}}\right)}$	يعتمد هذا النظام على خوارزمية شبه متعددة الحدود من أهوجا وأورلين وتارجان. وهو أسرع من خوارزميات كينج وراو وتارجان، ولا يستخدم أشجار الربط/القطع، ولكنه ليس أسرع من خوارزمية أورلين + KRT.

بالتوازي مع تطوير خوارزميات التدفق متعددة الحدود القوية، كان هناك سلسلة طويلة من حدود الوقت شبه متعددة الحدود وحدود الوقت متعددة الحدود الضعيفة، والتي يعتمد وقت تشغيلها على حجم سعات الإدخال. هنا، القيمة${\displaystyle U}$يشير هذا إلى أكبر سعة للحافة بعد إعادة تحجيم جميع السعات إلى قيم صحيحة . (إذا كانت الشبكة تحتوي على سعات غير نسبية ، فقد لا تكون إعادة التحجيم هذه ممكنة، وقد لا تُنتج هذه الخوارزميات حلولًا دقيقة، أو قد تفشل في التقارب حتى إلى حل تقريبي). الفرق بين كثير الحدود الزائف وكثير الحدود الضعيف هو أن حد كثير الحدود الزائف قد يكون كثير الحدود في ${\displaystyle U}$لكن بالنسبة للحد متعدد الحدود الضعيف، يمكن أن يكون متعدد الحدود فقط في${\displaystyle \log U}$.

طريقة	سنة	تعقيد	وصف
خوارزمية فورد-فولكرسون [ 34 ]	1956	${\displaystyle O(EU)}$	طالما أن هناك مسارًا مفتوحًا عبر الرسم البياني المتبقي، أرسل الحد الأدنى من السعات المتبقية على ذلك المسار.
خوارزمية التدفق الثنائي الحجب [ 35 ]	1998	${\displaystyle O\left(E\cdot \min\{V^{2/3},E^{1/2}\}\cdot \log {\frac {V^{2}}{E}}\cdot \log U\right)}$
خوارزمية كاثوريا-ليو-سيدفورد [ 36 ]	2020	${\displaystyle E^{4/3+o(1)}U^{1/3}}$	أساليب النقاط الداخلية وتعزيز الحواف باستخدام${\displaystyle \ell _{p}}$تدفقات المعيار -norm. يعتمد على خوارزمية سابقة لمادري، والتي حققت وقت تشغيل${\displaystyle {\tilde {O}}(E^{10/7}U^{1/7})}$[ 37 ]​
خوارزمية BLNPSSSW / BLLSSSW [ 38 ] [ 39 ]	2020	${\displaystyle {\tilde {O}}((E+V^{3/2})\log U)}$	أساليب النقاط الداخلية والصيانة الديناميكية للتدفقات الكهربائية مع تفكيكات الموسع.
خوارزمية غاو-ليو-بينغ [ 40 ]	2021	${\displaystyle {\tilde {O}}(E^{{\frac {3}{2}}-{\frac {1}{328}}}\log U)}$	تتمحور خوارزمية غاو، ليو، وبينغ حول الحفاظ الديناميكي على التدفقات الكهربائية المتزايدة في صميم الخوارزمية القائمة على طريقة النقطة الداخلية من [Mądry JACM '16]. ويتضمن ذلك تصميم هياكل بيانات تُعيد، في ظروف محدودة، حوافًا ذات طاقة كهربائية كبيرة في رسم بياني يخضع لتحديثات المقاومة.
خوارزمية تشين وكينج وليو وبنغ وجوتنبرج وساتشديفا [ 10 ]	2022	${\displaystyle E^{1+o(1)}\log U}$عشوائي لم يُذكر مستوى التعقيد بدقة في الورقة البحثية، ولكنه يبدو كذلك.${\displaystyle E\exp O(\log ^{7/8}E\log \log E)\log U}$	تحل خوارزمية تشين، وكينغ، وليو، وبينغ، وغوتنبرغ، وساشديفا مسألة التدفق الأقصى والتدفق ذي التكلفة الأدنى في وقت خطي تقريبًا عن طريق بناء التدفق من خلال سلسلة من${\displaystyle E^{1+o(1)}}$دورات تقريبية غير موجهة ذات نسبة دنيا، يتم حساب كل منها ومعالجتها في استهلاك${\displaystyle E^{o(1)}}$الوقت باستخدام بنية بيانات ديناميكية.
فان دن براند وآخرون [ 41 ]	2023	${\displaystyle E^{1+o(1)}\log U}$حتمية	تحقق الخوارزمية التي وضعها فان دن براند وآخرون نفس التعقيد التقاربي الذي حققته خوارزمية تشين وآخرون، لكنها خوارزمية حتمية، أي أنها ليست عشوائية.
بيرنشتاين، بليكستاد، سارانوراك، تو [ 42 ]	2024	${\displaystyle O(n^{2+o(1)}\log U)}$خوارزمية عشوائية عندما تأتي سعات الحواف من المجموعة${\displaystyle \{1,\dots ,U\}}$	تُعدّ هذه الخوارزمية نسخةً معدّلة من خوارزمية الدفع وإعادة التسمية، وذلك بإدخال النسخة الموزونة . وعلى عكس مناهج تشين وآخرون، أو فان دن براند وآخرون، فإنّ هذه الخوارزمية هي خوارزمية توافقية تعتمد على توسيع المسارات . تُحدّد هذه الورقة البحثية دالة وزن على الرسوم البيانية الموجهة وغير الدورية (DAG)، وتحاول محاكاتها على الرسوم البيانية العامة باستخدام التسلسلات الهرمية الموسّعة الموجهة، والتي تُنتج ترتيبًا طبيعيًا للرؤوس يُنتج دالة وزن مشابهة لتلك الخاصة بالحالة الخاصة من الرسوم البيانية الموجهة وغير الدورية. جانب العشوائية (وبالتالي،${\displaystyle n^{o(1)}}$ينشأ هذا العامل من صعوبة تطبيق التسلسلات الهرمية الموجهة للتوسيع على حساب القطع المتفرقة ، والتي لا تسمح بالتحديث الديناميكي الطبيعي.

بالنظر إلى شبكة${\displaystyle N=(V,E)}$مع مجموعة من المصادر${\displaystyle S=\{s_{1},\ldots ,s_{n}\}}$ومجموعة من الأحواض${\displaystyle T=\{t_{1},\ldots ,t_{m}\}}$بدلاً من مصدر واحد ومصب واحد فقط، علينا إيجاد أقصى تدفق عبر${\displaystyle N}$يمكننا تحويل مشكلة المصادر المتعددة والمصارف المتعددة إلى مشكلة التدفق الأقصى عن طريق إضافة مصدر موحد يتصل بكل رأس في${\displaystyle S}$ومصرف موحد متصل بكل رأس في${\displaystyle T}$(المعروفة أيضًا باسم المصدر الفائق والمصب الفائق ) بسعة لا نهائية على كل حافة (انظر الشكل 4.1.1).

بالنظر إلى رسم بياني ثنائي الأجزاء${\displaystyle G=(X\cup Y,E)}$علينا إيجاد تطابق ذي عدد عناصر أقصى في${\displaystyle G}$أي أنها مطابقة تحتوي على أكبر عدد ممكن من الحواف. يمكن تحويل هذه المشكلة إلى مشكلة تدفق أقصى عن طريق إنشاء شبكة.${\displaystyle N=(X\cup Y\cup \{s,t\},E')}$، أين

1. ${\displaystyle E'}$يحتوي على الحواف في${\displaystyle G}$موجه من${\displaystyle X}$ل${\displaystyle Y}$.
2. ${\displaystyle (s,x)\in E'}$لكل${\displaystyle x\in X}$و${\displaystyle (y,t)\in E'}$لكل${\displaystyle y\in Y}$.
3. ${\displaystyle c(e)=1}$لكل${\displaystyle e\in E'}$(انظر الشكل 4.3.1).

ثم قيمة التدفق الأقصى في${\displaystyle N}$يساوي حجم المطابقة القصوى في${\displaystyle G}$ويمكن إيجاد تطابق ذي عدد عناصر أقصى عن طريق أخذ تلك الحواف التي لها تدفق${\displaystyle 1}$في تدفق أقصى متكامل.

بالنظر إلى رسم بياني موجه غير دوري${\displaystyle G=(V,E)}$المطلوب إيجاد أقل عدد من المسارات المنفصلة عن الرؤوس لتغطية كل رأس في${\displaystyle V}$يمكننا إنشاء رسم بياني ثنائي الأجزاء${\displaystyle G'=(V_{\textrm {out}}\cup V_{\textrm {in}},E')}$من${\displaystyle G}$، أين

1. ${\displaystyle V_{\textrm {out}}=\{v_{\textrm {out}}\mid v\in V\land v{\text{ has outgoing edge(s)}}\}}$
2. ${\displaystyle V_{\textrm {in}}=\{v_{\textrm {in}}\mid v\in V\land v{\text{ has incoming edge(s)}}\}}$
3. ${\displaystyle E'=\{(u_{\textrm {out}},v_{\textrm {in}})\in V_{out}\times V_{in}\mid (u,v)\in E\}}$.

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

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

1. كل رأس${\displaystyle v_{\textrm {out}}}$في${\displaystyle G'}$يمكن أن يكون غير متطابق في${\displaystyle M}$وفي هذه الحالة لا توجد حواف صادرة${\displaystyle v}$في${\displaystyle C}$أو يمكن مطابقتها ، وفي هذه الحالة يكون هناك حافة واحدة فقط ناشئة${\displaystyle v}$في${\displaystyle C}$في كلتا الحالتين، لا يخرج من أي رأس أكثر من حافة واحدة${\displaystyle v}$في${\displaystyle C}$.
2. وبالمثل بالنسبة لكل رأس${\displaystyle v_{\textrm {in}}}$في${\displaystyle G'}$- إذا تمت مطابقته، فهناك حافة واردة واحدة إلى${\displaystyle v}$في${\displaystyle C}$؛ خلاف ذلك${\displaystyle v}$لا توجد حواف واردة في${\displaystyle C}$.

وبالتالي لا يوجد رأس له حافتان واردتان أو حافتان صادرتان في${\displaystyle C}$وهذا يعني جميع المسارات في${\displaystyle C}$هي منفصلة عن بعضها البعض من حيث الرؤوس.

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

يترك${\displaystyle N=(V,E)}$لنفترض أن لدينا شبكة. ولنفترض أن هناك سعة عند كل عقدة بالإضافة إلى سعة الحافة، أي تعيين${\displaystyle c:V\to \mathbb {R} ^{+},}$بحيث يكون التدفق${\displaystyle f}$يجب أن يفي ليس فقط بقيد السعة وحفظ التدفقات، ولكن أيضًا بقيد سعة الرأس.

${\displaystyle \sum _{i\in V}f_{iv}\leq c(v)\qquad \forall v\in V\backslash \{s,t\}.}$

بمعنى آخر، لا يمكن أن تتجاوز كمية التدفق المار عبر رأس ما سعته. لإيجاد أقصى تدفق عبر${\displaystyle N}$يمكننا تحويل المشكلة إلى مشكلة التدفق الأقصى بالمعنى الأصلي عن طريق التوسيع${\displaystyle N}$أولاً، كل${\displaystyle v\in V}$يتم استبدالها بـ${\displaystyle v_{\text{in}}}$و${\displaystyle v_{\text{out}}}$، أين${\displaystyle v_{\text{in}}}$متصلة بحواف تدخل إلى${\displaystyle v}$و${\displaystyle v_{\text{out}}}$متصل بالحواف الخارجة من${\displaystyle v}$ثم قم بتخصيص السعة${\displaystyle c(v)}$إلى الحافة المتصلة${\displaystyle v_{\text{in}}}$و${\displaystyle v_{\text{out}}}$(انظر الشكل 4.4.1). في هذه الشبكة الموسعة، يتم إزالة قيد سعة الرأس، وبالتالي يمكن التعامل مع المشكلة على أنها مشكلة التدفق الأقصى الأصلية.

بالنظر إلى رسم بياني موجه${\displaystyle G=(V,E)}$ورأسين${\displaystyle s}$و${\displaystyle t}$المطلوب إيجاد أكبر عدد من المسارات من${\displaystyle s}$ل${\displaystyle t}$لهذه المشكلة عدة أشكال:

1. يجب أن تكون المسارات منفصلة الحواف. يمكن تحويل هذه المشكلة إلى مشكلة تدفق أقصى عن طريق إنشاء شبكة${\displaystyle N=(V,E)}$من${\displaystyle G}$، مع${\displaystyle s}$و${\displaystyle t}$كونها المصدر والمصب${\displaystyle N}$على التوالي، وتخصيص سعة لكل حافة من${\displaystyle 1}$في هذه الشبكة، يكون التدفق الأقصى هو${\displaystyle k}$إذا كان هناك${\displaystyle k}$مسارات منفصلة الحواف.

2. يجب أن تكون المسارات مستقلة، أي منفصلة الرؤوس (باستثناء${\displaystyle s}$و${\displaystyle t}$يمكننا إنشاء شبكة.${\displaystyle N=(V,E)}$من${\displaystyle G}$بسعات الرؤوس، حيث تكون سعات جميع الرؤوس وجميع الحواف${\displaystyle 1}$ثم تكون قيمة التدفق الأقصى مساوية لأكبر عدد من المسارات المستقلة من${\displaystyle s}$ل${\displaystyle t}$.

3. بالإضافة إلى كون المسارات منفصلة الحواف و/أو منفصلة الرؤوس، فإن للمسارات أيضًا قيدًا على الطول: فنحن نحسب فقط المسارات التي يكون طولها بالضبط${\displaystyle k}$أو على الأكثر${\displaystyle k}$معظم صيغ هذه المسألة هي مسائل NP-كاملة ، باستثناء القيم الصغيرة لـ${\displaystyle k}$[ ^{43 ]​}

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

في مسألة إقصاء الفرق في لعبة البيسبول، _يتنافس n فريقًا في دوري. في مرحلة معينة من الموسم، يُمثل wᵢ عدد انتصارات الفريق i، و rᵢ عدد المباريات المتبقية له ، و _rᵢⱼ عدد المباريات المتبقية ضد الفريق j . يُقصى الفريق إذا لم تكن لديه _أي فرصة لإنهاء الموسم. تكمن مهمة مسألة إقصاء الفرق في تحديد الفرق التي تُقصى في كل مرحلة من مراحل الموسم. اقترح شوارتز ^{[ 44 ]} طريقةً تُختزل هذه المسألة إلى مسألة تدفق الشبكة الأقصى. في هذه الطريقة، تُنشأ شبكة لتحديد ما إذا كان الفريق k سيُقصى أم لا.

لنفترض أن G = ( V , E ) هي شبكة، حيث s و t ∈ V هما المصدر والمصب على التوالي. نضيف عقدة لعبة _ij ، التي تمثل عدد مرات اللعب بين هذين الفريقين. نضيف أيضًا عقدة فريق لكل فريق، ونربط كل عقدة لعبة { i , j } حيث i < j بـ V ، ونربط كل عقدة منها من s بحافة سعتها r_{_ij}، التي تمثل عدد مرات اللعب بين هذين الفريقين. نضيف أيضًا عقدة فريق لكل فريق، ونربط كل عقدة لعبة { i , j } بعقدتي فريق i و j لضمان فوز أحدهما. لا حاجة لتقييد قيمة التدفق على هذه الحواف. أخيرًا، تُنشأ حواف من عقدة الفريق i إلى عقدة المصب t ، وتُضبط سعة w _{_k} + r _{_k} - w _{_i} لمنع الفريق i من الفوز بأكثر من w _{_k} + r _{_k} . لنفترض أن S هي مجموعة جميع الفرق المشاركة في الدوري، و

${\displaystyle r(S-\{k\})=\sum _{i,j\in \{S-\{k\}\} \atop i<j}r_{ij}}$.

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

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

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

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

1. حافة ذات سعة [0، 1] بين s وكل s _i .
2. حافة ذات سعة [0، 1] بين كل d _i و t .
3. حافة ذات سعة [1، 1] بين كل زوج من s _i و d _i .
4. حافة ذات سعة [0، 1] بين كل d _i و s _j ، إذا كان المصدر s _j يمكن الوصول إليه بمدة زمنية وتكلفة معقولة من وجهة الرحلة i .
5. حافة ذات سعة [0, ∞ ] بين s و t .

في الطريقة المذكورة، يُزعم ويُثبت أن إيجاد قيمة تدفق k في G بين s و t يساوي إيجاد جدول زمني ممكن لمجموعة الرحلات F مع طاقم لا يزيد عن k . ^{[ 45 ]}

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

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

1. أضف عقدة مصدر s وأضف حوافًا منها إلى كل عقدة مصنع f _i بسعة p _i حيث p _i هو معدل إنتاج المصنع f _i .
2. أضف عقدة مصب t وأضف حوافًا من جميع القرى v _i إلى t بسعة d _i حيث d _i هو معدل الطلب للقرية v _i .

لنفترض أن G = ( V , E ) هي هذه الشبكة الجديدة. يوجد مسار دوران يلبي الطلب إذا وفقط إذا  :

قيمة التدفق القصوى ( G )${\displaystyle =\sum _{i\in v}d_{i}}$.

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

يمكن توسيع نطاق المشكلة بإضافة حد أدنى للتدفق على بعض الحواف. ^{[ 46 ]}

في كتابهما، يقدم كلاينبرغ وتاردوس خوارزمية لتقسيم الصورة. ^{[ 48 ]} يقدمان خوارزمية لتحديد الخلفية والمقدمة في الصورة. وبشكل أدق، تأخذ الخوارزمية صورة نقطية كمدخل، مُنمذجة على النحو التالي: aᵢ ≥ ₀ هو احتمال انتماء البكسل i إلى المقدمة، _و bᵢ ≥ ₀ هو احتمال انتماء البكسل i إلى الخلفية، و pᵢⱼ هو الجزاء في حالة وضع بكسلين متجاورين i و j أحدهما في المقدمة والآخر في الخلفية. الهدف هو إيجاد تقسيم ( A , B ) لمجموعة البكسلات التي تُعظّم الكمية التالية

${\displaystyle q(A,B)=\sum _{i\in A}a_{i}+\sum _{i\in B}b_{i}-\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}$،

في الواقع، بالنسبة للبكسلات في المجموعة A (التي تُعتبر المقدمة)، نحصل على a _i ؛ وبالنسبة لجميع البكسلات في المجموعة B (التي تُعتبر الخلفية)، نحصل على b _i . على الحدود، بين بكسلين متجاورين i و j ، نفقد p _ij . وهذا يُكافئ تقليل الكمية

${\displaystyle q'(A,B)=\sum _{i\in A}b_{i}+\sum _{i\in B}a_{i}+\sum _{\begin{matrix}i,j{\text{ adjacent}}\\|A\cap \{i,j\}|=1\end{matrix}}p_{ij}}$

لأن

${\displaystyle q(A,B)=\sum _{i\in A\cup B}a_{i}+\sum _{i\in A\cup B}b_{i}-q'(A,B).}$

نقوم الآن بإنشاء الشبكة التي تتكون عقدها من البكسل، بالإضافة إلى مصدر ومصب، كما هو موضح في الشكل على اليمين. نربط المصدر بالبكسل i بواسطة حافة وزنها a _i . نربط البكسل i بالمصب بواسطة حافة وزنها b _i . نربط البكسل i بالبكسل j بواسطة حافة وزنها p _ij . الآن، يتبقى حساب القطع الأدنى في تلك الشبكة (أو ما يعادله، التدفق الأقصى). يوضح الشكل الأخير القطع الأدنى.