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

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

بالنظر إلى الرسم البياني ثنائي الأجزاء ${\displaystyle G=(X\cup Y,E)}$، فإن الهدف هو إيجاد الحد الأقصى لعدد العناصر المتطابقة في 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).

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

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

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

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

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

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

بعبارة أخرى، يجب ألا تتجاوز كمية التدفق العابر لأي رأس في الشبكة سعته المحددة. ولإيجاد الحد الأقصى للتدفق عبر الشبكة N، يمكننا تحويل هذه المسألة إلى مشكلة تدفق أقصى بالمعنى التقليدي من خلال توسيع الشبكة 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)}$ ورأسين محددين s و t، فإن الهدف هو إيجاد الحد الأقصى لعدد المسارات المنفصلة من s إلى t. لهذه المسألة عدة صور:

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

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

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

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

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

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

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

لنفترض أن G = (V, E) هي شبكة، حيث يمثل s و t عقدتي المصدر والمصب الرئيسيتين في V. لكل رحلة i، ذات مصدر ووجهة محددتين، نضيف عقدتين جديدتين إلى V: العقدة sᵢ لتمثيل مصدر الرحلة i، والعقدة dᵢ لتمثيل وجهة الرحلة 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 طاقم كحد أقصى. . ^[2]

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

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

1. أضف عقدة مصدر s وأضف حوافًا منها إلى كل عقدة مصنع f_i بسعة p_i حيث p_i هو معدل إنتاج المصنع f_i .
2. أضف عقدة الحوض t وأضف الحواف من جميع القرى v_i إلى t بسعة d_i حيث d_i هو معدل الطلب للقرية v_i .

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

Maximum flow value(G) ${\displaystyle =\sum _{i\in v}d_{i}}$.

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

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

في كتابهما، يقدم كلاينبيرج وتاردوس خوارزمية لمعالجة مشكلة تقسيم الصور. ^[5] تحديدًا، يقترحون خوارزمية لتحديد مناطق الخلفية والمقدمة في الصورة. وبشكل أكثر دقة، تستقبل الخوارزمية خريطة من البيانات الثنائية (بتات) كمدخل، ويتم تمثيل هذه البيانات على النحو التالي: aᵢ ≥ 0 يمثل احتمالية انتماء البكسل i إلى منطقة المقدمة، و bᵢ ≥ 0 يمثل احتمالية انتماء البكسل i إلى منطقة الخلفية، بينما تمثل pᵢⱼ قيمة العقوبة المترتبة على وضع بكسلين متجاورين i و j في منطقتين مختلفتين (أحدهما في المقدمة والآخر في الخلفية). الهدف من الخوارزمية هو إيجاد تقسيم (A, B) لمجموعة البكسلات يحقق أقصى قيمة للمقدار التالي:

${\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}}$

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

${\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 إلى المصب بوزن قدره bᵢ. كما ننشئ حافة غير موجهة بين أي بكسلين متجاورين i و j بوزن قدره pᵢⱼ. الآن، يبقى علينا حساب الحد الأدنى للقطع في هذه الشبكة (أو ما يكافئه من تدفق أقصى). ويوضح الشكل الأخير الحد الأدنى لهذا القطع.