ما معنى Network Flow ودالة التدفق (Flow Function) في الخوارزميات وهياكل البيانات
إذا صادفتَ عبارة «network flow: see flow function» في قاموس خوارزميات أو مسرد مصطلحات (مثل معجم NIST للخوارزميات وهياكل البيانات)، فلا تقلق: هذه ليست خوارزمية غامضة، بل مجرد إحالة مرجعية. المسرد يقول لك: «لفهم مصطلح تدفق الشبكة (Network Flow)، ارجع إلى تعريف دالة التدفق (Flow Function)». بعبارة أخرى، المصطلحان مترابطان: تدفق الشبكة هو المسألة العامة، ودالة التدفق هي الأداة الرياضية التي تصف الحل. في هذا المقال نفكّك المفهومين بلغة بسيطة، ثم نمرّ على أشهر خوارزميات حلّهما.
ما هو تدفق الشبكة (Network Flow)؟
تخيّل شبكة أنابيب مياه، أو شبكة طرق لنقل البضائع، أو كابلات إنترنت. لديك مصدر (Source) يضخّ المادة، ومصبّ (Sink) يستقبلها، وبينهما عقد ومسارات لكل منها سعة قصوى (Capacity) لا يمكن تجاوزها. السؤال الجوهري: ما أقصى كمية يمكن نقلها من المصدر إلى المصبّ في وقت واحد دون تجاوز سعة أي مسار؟ هذه هي مسألة أقصى تدفق (Maximum Flow)، وهي جوهر موضوع تدفق الشبكة في نظرية الرسوم البيانية.
نمثّل الشبكة رياضيًا كرسم بياني موجّه:
- الرؤوس (Nodes/Vertices): نقاط الالتقاء أو التفرّع.
- الحواف (Edges): المسارات الموجّهة بين الرؤوس.
- السعة (Capacity): الحد الأقصى للتدفق عبر كل حافة.
ما هي دالة التدفق (Flow Function)؟
دالة التدفق هي الدالة التي تُسنِد لكل حافة في الشبكة قيمة رقمية تمثّل كمية المادة الفعلية المارّة عبرها في لحظة معيّنة. لكي تكون الدالة صحيحة (تدفقًا مقبولًا)، يجب أن تحقق شرطين أساسيين:
- قيد السعة: التدفق عبر أي حافة لا يتجاوز أبدًا سعتها القصوى (ولا يكون سالبًا).
- حفظ التدفق (Conservation): عند أي عقدة وسيطة (غير المصدر والمصبّ)، مجموع الداخل يساوي مجموع الخارج تمامًا — لا يتراكم شيء ولا يضيع، تمامًا كأنبوب ماء لا يتسرّب.
قيمة التدفق (Flow Value) هي صافي ما يخرج من المصدر (أو ما يصل إلى المصبّ). وهدف مسألة أقصى تدفق هو إيجاد دالة تدفق تجعل هذه القيمة أكبر ما يمكن. لهذا يقول المسرد «راجع دالة التدفق»: لأنها التعريف الدقيق الذي تُبنى عليه المسألة كلها.
نظرية أساسية: أقصى تدفق = أدنى قطع
من أجمل النتائج في هذا المجال مبرهنة أقصى تدفق–أدنى قطع (Max-Flow Min-Cut). تقول إن أكبر قيمة تدفق ممكنة تساوي تمامًا سعة أصغر «قطع» يفصل المصدر عن المصبّ. القطع هنا هو مجموعة الحواف التي لو أزلتها لانقطع الطريق كليًا بين الطرفين. هذه المبرهنة ليست مجرد فضول نظري؛ بل هي الأساس الذي تعتمد عليه خوارزميات الحل للتحقق من أنها وصلت فعلًا إلى الحدّ الأقصى.
أشهر خوارزميات حساب أقصى تدفق
الفكرة المشتركة بين معظمها هي البحث عن مسار زيادة (Augmenting Path): طريق من المصدر إلى المصبّ ما زالت فيه سعة متبقية، فنضخّ عبره مزيدًا من التدفق، ونكرّر حتى لا يبقى أي مسار. إليك مقارنة سريعة:
| الخوارزمية | كيف تختار المسار | التعقيد الزمني | ملاحظة |
|---|---|---|---|
| فورد-فولكرسون (Ford-Fulkerson) | أي مسار زيادة متاح | يعتمد على قيم السعات | بسيطة لكنها قد تبطؤ مع سعات كبيرة |
| إدموندز-كارب (Edmonds-Karp) | أقصر مسار عبر بحث بالعرض BFS | O(V·E²) | تحسين مضمون لا يعتمد على قيم السعة |
| دفع-وإعادة تسمية (Push-Relabel) | تدفع محليًا ثم تعيد ترتيب الرؤوس | O(V²·√E) أو أفضل | الأسرع عمليًا في الشبكات الكثيفة |
| دينيتش (Dinic) | مسارات في «رسم بياني طبقي» | O(V²·E) | ممتازة، وفعّالة جدًا على شبكات التوفيق |
نصيحة عملية: لا تكتب هذه الخوارزميات من الصفر في مشروع حقيقي. مكتبات جاهزة مثل NetworkX في بايثون أو Boost Graph في C++ مُختبَرة ومُحسَّنة. اكتبها بنفسك فقط للتعلّم أو في المسابقات البرمجية.
أين تُستخدم مسائل التدفق فعليًا؟
- التوفيق الثنائي (Bipartite Matching): توزيع الموظفين على المهام، أو الطلاب على المشاريع — تُحوَّل إلى مسألة تدفق.
- الشبكات اللوجستية: تخطيط نقل البضائع بأقل ازدحام.
- شبكات الاتصالات: توجيه حزم البيانات لتقليل الاختناق.
- معالجة الصور: فصل الكائن عن الخلفية عبر «القطع الأدنى».
- جدولة الموارد وتخطيط الإنتاج.
خطأ شائع يقع فيه المبتدئون: الخلط بين أقصى تدفق وأقصر مسار. أقصر مسار يبحث عن أرخص طريق واحد، أما أقصى تدفق فيستغلّ كل المسارات معًا في آنٍ واحد. كما يخلط البعض بين أقصى تدفق وتدفق بأقل تكلفة (Min-Cost Flow)؛ الثاني يضيف كلفةً لكل حافة ويطلب أرخص طريقة لتمرير كمية محددة.
الأسئلة الشائعة
هل «network flow» و«flow function» شيئان مختلفان؟ لا جوهريًا. «تدفق الشبكة» اسم المسألة والمجال، و«دالة التدفق» هي التعريف الرياضي الذي يصف توزيع التدفق على الحواف. المسرد يحيلك من الأول إلى الثاني لأن فهم الثاني ضروري لفهم الأول.
ما الفرق بين فورد-فولكرسون وإدموندز-كارب؟ كلاهما يستخدم مسارات الزيادة. الفرق أن إدموندز-كارب يحدّد قاعدة صارمة: اختر دائمًا أقصر مسار (عبر BFS)، ما يضمن زمن تنفيذ O(V·E²) مستقلًا عن قيم السعات، بينما قد تتباطأ فورد-فولكرسون العامة مع سعات ضخمة.
هل أحتاج رياضيات متقدمة لفهم الموضوع؟ تكفيك أساسيات نظرية الرسوم البيانية ومفهوما المصدر والمصبّ والسعة. الرسم على ورقة لشبكة صغيرة وتتبّع التدفق يدويًا هو أسرع طريقة للاستيعاب.
أي خوارزمية أختار للتطبيق العملي؟ للشبكات المتوسطة، خوارزمية دينيتش توازن جيدًا بين البساطة والأداء. للشبكات الكثيفة والكبيرة، Push-Relabel غالبًا الأسرع. وفي كل الأحوال، ابدأ بمكتبة جاهزة قبل كتابة كودك الخاص.