مبرهنة التدفق الأقصى والقطع الأدنى

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

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

هذه حالة خاصة من نظرية الثنائية للبرامج الخطية ويمكن استخدامها لاستنتاج نظرية مينجر ونظرية كونيج-إيجرفاري.^[1]

التعاريف والبيان

تساوي النظرية بين كميتين: الحد الأقصى للتدفق عبر شبكة، والحد الأدنى لسعة جزء من الشبكة. ولتوضيح هذه النظرية، لا بد من تعريف كل من هذه المفاهيم أولاً.

شبكة

تتكون الشبكة من

الرسم البياني الموجه المحدود $G = (V, E)$ ، حيث يشير V إلى المجموعة المحدودة من الرؤوس و $E \subseteq V \times V$ هي مجموعة الحواف الموجهة؛
مصدر $s \in V$ ومصرف $t \in V$ ؛
دالة السعة، وهي عبارة عن تعيين $c:E\to \mathbb {R} ^{+}$ يُشار إليه بـ $c uv$ أو $c (u, v)$ لـ $(u, v) \in E$ . وهو يمثل أقصى كمية تدفق يمكن أن تمر عبر الحافة.

التدفقات

التدفق عبر الشبكة هو رسم خرائط $f:E\to \mathbb {R} ^{+}$ يُشار إليه بـ $f_{uv}$ أو $f(u,v)$ ، مع مراعاة القيود التالية:

قيد السعة : لكل حافة $(u,v)\in E$ ، $f_{uv}\leq c_{uv}.$
حفظ التدفقات : لكل رأس $v$ بعيدا $s$ و $t$ (أي المصدر والمصرف، على التوالي)، تنطبق المساواة التالية:

$\sum \nolimits _{\{u:(u,v)\in E\}}f_{uv}=\sum \nolimits _{\{w:(v,w)\in E\}}f_{vw}.$

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

تُحدد قيمة التدفق بواسطة

|f|=\sum \nolimits _{\{v:(s,v)\in E\}}f_{sv}=\sum \nolimits _{\{v:(v,t)\in E\}}f_{vt},

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

مشكلة التدفق الأقصى. تعظيم $|f|$ ، أي توجيه أكبر قدر ممكن من التدفق من $s$ ل $t$ .

القطع

يشير النصف الآخر من نظرية الحد الأقصى للتدفق والحد الأدنى للقطع إلى جانب مختلف من الشبكة: مجموعة القطع. القطع الثابت $C = (S, T)$ هو تقسيم لـ $V$ بحيث $s \in S$ و $t \in T$ . أي أن القطع الثابت s - t هو تقسيم رؤوس الشبكة إلى قسمين، حيث يكون المصدر في أحد القسمين والمصرف في القسم الآخر. مجموعة القطع $X_{C}$ من القطع $C$ هي مجموعة الحواف التي تربط جزء المصدر من القطع بجزء الحوض:

X_{C}:=\{(u,v)\in E\ :\ u\in S,v\in T\}=(S\times T)\cap E.

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

سعة القطع هي مجموع سعات الحواف في مجموعة القطع الخاصة بها،

c(S,T)=\sum \nolimits _{(u,v)\in X_{C}}c_{uv}=\sum \nolimits _{(i,j)\in E}c_{ij}d_{ij},

حيث $d_{ij}=1$ لو $i\in S$ و $j\in T$ ، $0$ خلاف ذلك.

عادةً ما يكون هناك العديد من القطع في الرسم البياني، ولكن القطع ذات الأوزان الأصغر غالبًا ما يكون من الصعب العثور عليها.

مشكلة القطع الأدنى. تقليل

c (S, T)

، أي تحديد

S

و

T

بحيث تكون سعة القطع st ضئيلة.

النظرية الرئيسية

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

نظرية الحد الأقصى للتدفق والحد الأدنى للقطع. القيمة القصوى لتدفق st تساوي الحد الأدنى للسعة على جميع قطع st.

مثال

يوضح الشكل الموجود على اليمين التدفق في الشبكة. يشير التعليق الرقمي على كل سهم، في النموذج f / c ، إلى التدفق ( f ) وسعة السهم ( c ). ويبلغ مجموع التدفقات الصادرة من المصدر خمسة (2+3=5)، كما يبلغ مجموع التدفقات إلى الحوض (2+3=5)، مما يؤكد أن قيمة التدفق هي 5.

يُعطى قطع s - t واحد بقيمة 5 بواسطة S ={ s, p } و T ={ o, q, r, t }. سعة الحواف التي تعبر هذا القطع هي 3 و 2، مما يعطي سعة قطع 3 + 2 = 5. (لا يؤخذ السهم من o إلى p في الاعتبار، لأنه يشير من T إلى S مرة أخرى)

قيمة التدفق تساوي سعة القطع، مما يدل على أن التدفق هو تدفق أقصى وأن القطع هو قطع أدنى.

لاحظ أن التدفق عبر كل من السهمين اللذين يربطان S بـ T يكون بكامل طاقته؛ وهذا هو الحال دائمًا: يمثل القطع الأدنى "عنق زجاجة" للنظام.

صياغة البرنامج الخطي

يمكن صياغة مشكلة التدفق الأقصى ومشكلة القطع الأدنى كبرنامجين خطيين ثنائيين أساسيين.^[2]

	التدفق الأقصى (أساسي)	القص الأدنى (مزدوج)
المتغيرات	$f_{uv}$ $\forall (u,v)\in E$ [متغيران لكل حافة، متغير في كل اتجاه]
constraints	يخضع لـ ${\begin{aligned}f_{uv}&\leq c_{uv}&&\forall (u,v)\in E\\\sum _{u}f_{uv}-\sum _{w}f_{vw}&=0&&v\in V\setminus \{s,t\}\end{aligned}}$ [قيد لكل حافة وقيد لكل عقدة غير طرفية]

مراجع

^ Dantzig، G.B.؛ Fulkerson، D.R. (9 سبتمبر 1964). "On the max-flow min-cut theorem of networks" (PDF). RAND Corporation: 13. مؤرشف من الأصل (PDF) في 2018-05-05.
^ Trevisan، Luca. "Lecture 15 from CS261: Optimization" (PDF).

[1] Dantzig، G.B.؛ Fulkerson، D.R. (9 سبتمبر 1964). "On the max-flow min-cut theorem of networks" (PDF). RAND Corporation: 13. مؤرشف من الأصل (PDF) في 2018-05-05.

[2] Trevisan، Luca. "Lecture 15 from CS261: Optimization" (PDF).

[1]

[2]