مرجع
آخر الزيارات

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

775 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: في علوم الكمبيوتر ونظرية التحسين، تنص نظرية الحد الأقصى للتدفق والحد الأدنى للقطع على أنه في شبكة التدفق، فإن الحد الأقصى لكمية التدفق التي تمر من المصدر إلى الحوض يساوي الوزن الإجمالي للحواف في الحد الأدنى للقطع، أي أصغر وزن إجمالي للحواف…. في هذه المقالة 8 أقسام: «التدفقات»، «تتكون الشبكة من» و«القطع» وغيرها.
المحتويات
  1. التدفقات
  2. تتكون الشبكة من
  3. القطع
  4. التعاريف والبيان
  5. النظرية الرئيسية
  6. مثال
  7. تُحدد قيمة التدفق بواسطة
  8. صياغة البرنامج الخطي

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

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

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

التدفقات

من جانب آخر، حفظ التدفقات : لكل رأس بعيدا و (أي المصدر والمصرف، على التوالي)، تنطبق المساواة التالية:

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

وفي هذا السياق، التدفق عبر الشبكة هو رسم خرائط يُشار إليه بـ أو ، مع مراعاة القيود التالية:

قيد السعة : لكل حافة ،

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

من جهة ثانية، الرسم البياني الموجه المحدود ، حيث يشير V إلى المجموعة المحدودة من الرؤوس و هي مجموعة الحواف الموجهة؛

مصدر ومصرف ؛

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

القطع

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

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

كذلك، يشير النصف الآخر من نظرية الحد الأقصى للتدفق والحد الأدنى للقطع إلى جانب مختلف من الشبكة: مجموعة القطع. القطع الثابت هو تقسيم لـ بحيث و . أي أن القطع الثابت s - t هو تقسيم رؤوس الشبكة إلى قسمين، حيث يكون المصدر في أحد القسمين والمصرف في القسم الآخر. مجموعة القطع من القطع هي مجموعة الحواف التي تربط جزء المصدر من القطع بجزء الحوض:

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

حيث لو و ، خلاف ذلك.

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

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

شبكة

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

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

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

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

مثال

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

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

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

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

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

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

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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