التدفق الأعظمي: اجمع ما يخرج من المصدر لا كل الحواف

الخلاصة السريعة

في مثالنا يخرج من المصدر A مقدار 3 إلى B ومقدار 2 إلى C، فتكون قيمة التدفق 3 + 2 = 5. يصل إلى المصب D مقدار 2 من B ومقدار 3 من C، أي 5 أيضًا. جمع تدفقات الحواف الخمس يعطي 11، لكنه يكرر عد الوحدات أثناء عبورها. التدفق 5 ممكن، وسعة الخروج من A تساوي 5، لذا هو الأعظمي هنا.

• في شبكة موجهة، لكل حافة سعة لا يتجاوزها تدفقها غير السالب. عند كل رأس داخلي، يجب أن يساوي مجموع التدفق الداخل مجموع الخارج. المصدر والمصب مستثنيان من شرط التساوي هذا. [1]
• في رسمنا A مصدر بلا أسهم داخلة، و D مصب بلا أسهم خارجة. تدفقات A→B و A→C و B→C و B→D و C→D هي 3 و 2 و 1 و 2 و 3؛ وتحفظ التساوي عند B و C.
• قيمة التدفق 5، وليست مجموع الحواف 11. مسارات A→B→D و A→C→D و A→B→C→D تحمل 2 و 2 و 1 على الترتيب؛ الوحدات نفسها تظهر على أكثر من حافة.
• سعتا الخروج من A هما 3 و 2، فلا يمكن أن تتجاوز القيمة 5. بنينا تدفقًا صحيحًا يبلغ 5، وهذا يثبت أنه الأعظمي في الشبكة الأصلية.
• القطع يقسم الرؤوس إلى جانب يضم المصدر وآخر يضم المصب؛ نجمع سعات الأسهم من جانب المصدر إلى الآخر فقط. [1] في قطع A,C إلى B,D السعة 3 + 3 = 6؛ لا نضيف B→C لأنه داخل إلى جانب المصدر.
• إذا خفضنا سعة B→D وحدها إلى 1، يصبح التدفق الأعظمي 4، مع بقاء سعة الخروج من A مساوية 5. حد المصدر وحده لا يضمن إمكان بلوغه؛ يلزم تدفق صحيح يحقق الحد.

ثبت المصدر والمصب والسعات قبل الحساب

نستخدم شبكة موجهة، لكل حافة فيها سعة وتدفق غير سالب لا يزيد عليها. ويتساوى الداخل والخارج عند الرؤوس الداخلية، مع استثناء المصدر والمصب. [1]

الرؤوس هي A و B و C و D. المصدر A لا يستقبل تدفقًا عبر أي حافة، والمصب D لا يخرج منه تدفق عبر أي حافة. الحواف الوحيدة هي A→B بسعة 3، و A→C بسعة 2، و B→C بسعة 1، و B→D بسعة 2، و C→D بسعة 3.

كل سهم يسمح في هذا النموذج بالعبور في اتجاه رأسه فقط. لا توجد حواف عكسية أو حلقات ذاتية أو حواف متوازية. الأرقام سعات صحيحة بوحدات مجردة؛ ليست مسافات أو أسعارًا أو قياسات ماء. السعة حد مسموح، والتدفق مقدار اخترناه داخل ذلك الحد.

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

تدفق صحيح يحفظ الكمية عند B و C

نختار تدفقات الحواف كما في الجدول:3 و 2 و 1 و 2 و 3 بالترتيب المعلن. تساوي كل قيمة سعة الحافة هنا، فلا يتجاوز أي تدفق الحد المسموح. لكن هذا الفحص وحده لا يكفي؛ نراجع الرأسين الداخليين أيضًا.

عند B يدخل 3 من A، ويخرج 1 إلى C و 2 إلى D. إذن الداخل 3 يساوي الخارج 1 + 2 = 3. وعند C يدخل 2 من A و 1 من B، ويخرج 3 إلى D؛ فيكون الداخل 2 + 1 = 3 مساويًا للخارج 3.

حقق الاختيار قيود الحواف وتساوي الداخل والخارج عند الرأسين الداخليين. لن نخلط بين السعة والتدفق: تطابقهما في هذا الاختيار خاص بالمثال، ولا يعني أن كل تدفق صحيح يجب أن يملأ كل حافة.

احسب الوحدات التي تغادر المصدر مرة واحدة

قيمة التدفق هي مجموع ما يخرج من المصدر في حالة عدم وجود حواف داخلة إليه، وتساوي ما يصل إلى المصب إذا لم تخرج منه حواف. [1]

تنطبق هذه الحالة على A و D في رسمنا. يخرج من A مقدار 3 + 2 = 5، ويصل إلى D مقدار 2 + 3 = 5. أما جمع تدفقات الحواف الخمس فيعطي 3 + 2 + 1 + 2 + 3 = 11. لماذا لا يمثل 11 مقدار الوحدات المنقولة من المصدر إلى المصب؟

نقسم التدفق المختار إلى ثلاثة مسارات: وحدتان عبر A→B→D، ووحدتان عبر A→C→D، ووحدة واحدة عبر A→B→C→D. مجموع الوحدات المنطلقة في هذه المسارات 2 + 2 + 1 = 5. هذه طريقة لوصف التدفق نفسه، وليست تدفقات نضيفها فوق قيم الجدول.

يتلقى السهم A→B وحدتين من المسار الأول ووحدة من الثالث، فيصبح تدفقه 3. ويتلقى C→D وحدتين من المسار الثاني ووحدة من الثالث، فيصبح 3 أيضًا. تبقى A→C عند 2 و B→D عند 2 و B→C عند 1، فتستعيد المسارات أرقام الجدول كلها.

المسار الأول يحمل وحدتين على حافتين، فتدخل مساهمة 4 في مجموع تدفقات الحواف. الثاني كذلك يساهم 4، والثالث يحمل وحدة على ثلاث حواف فيساهم 3. يصبح هذا المجموع 4 + 4 + 3 = 11؛ إنه عد لعبور الحواف، لا عد جديد للوحدات الخارجة من A.

أثبت القيمة القصوى، ثم انتبه لاتجاه القطع

بما أن A لا يملك سوى حافتي الخروج بسعتي 3 و 2، فلا يستطيع إرسال أكثر من 5. وقد أعطينا تدفقًا صحيحًا يبلغ 5 بالفعل. اجتماع حد أعلى 5 واختيار يحققه يثبت أن 5 هي أكبر قيمة ممكنة في رسمنا، دون الحاجة إلى تجربة كل اختيار.

يضع القطع المصدر في جانب والمصب في الجانب الآخر؛ وسعته مجموع سعات الحواف المتجهة من جانب المصدر إلى الآخر. قيمة أي تدفق لا تتجاوز سعة أي قطع، وأكبر قيمة تدفق تساوي أصغر سعة قطع. [1]

لدينا رأسان داخليان فقط،B و C؛ يمكن وضع كل منهما في أحد الجانبين، فتوجد أربعة اختيارات لجانب المصدر. يعرض الجدول جميعها. جانب المصب هو بقية الرؤوس في كل صف، ويضم D دائمًا. أقل سعة بين الصفوف 5، وتحققها ثلاثة قطوع؛ ليس القطع الأدنى فريدًا هنا.

في الصف الذي يضع A و C في جانب المصدر، يخرج A→B بسعة 3 ويخرج C→D بسعة 3، فتكون سعة القطع 3 + 3 = 6. السهم B→C يتجه بالعكس، من جانب المصب إلى جانب المصدر، لذلك لا يدخل في سعة هذا القطع. جمعه معها يعطي 7 ويغير تعريف ما نحسبه.

ومع التدفق المختار، يخرج عبر ذلك الحد 3 + 3 = 6، ويدخل عبره 1 على B→C. الصافي 6 − 1 = 5 يوافق قيمة التدفق. لا تتعارض سعة القطع 6 مع القيمة 5؛ لم نقل إن كل قطع له أصغر سعة. الصورة الداخلية تميز الأسهم الخارجة عن السهم الداخل وتحتفظ بالسعات الأصلية.

قد تبقى سعة المصدر 5 ويصبح الأعظمي 4

نغير سعة B→D وحدها من 2 إلى 1، ونبقي سعات الحواف الأخرى كما هي. لا تزال سعة الخروج من A تساوي 5، لكن D يستقبل الآن عبر حافتين سعتهما 1 و 3 فقط؛ فلا يصل إليه أكثر من 1 + 3 = 4.

نبني تدفقًا جديدًا بالقيم A→B:2، و A→C:2، و B→C:1، و B→D:1، و C→D:3. كل قيمة ضمن سعة حافتها المعدلة. عند B يدخل 2 ويخرج 1 + 1 = 2، وعند C يدخل 2 + 1 = 3 ويخرج 3. يخرج من A مقدار 2 + 2 = 4 ويصل إلى D مقدار 1 + 3 = 4.

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

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