شبكة التدفق

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

تعريف

الشبكة هي رسم بياني موجه $G$ $= ($ $V$ $,$ $E$ $) ذو$ دالة سعة غير سالبة $c$ لكل حافة، وبدون أقواس متعددة (أي حواف لها نفس عقدة المصدر والهدف). وبدون فقدان للعمومية ، يمكننا افتراض أنه إذا كان $($ $u$ $,$ $v$ $) \in$ $E$ ، فإن $($ $v$ $,$ $u$ $)$ هو أيضًا عنصر من $E.$ بالإضافة إلى ذلك، إذا كان $($ $v$ $,$ $u$ $) \notin$ $E$ ، فيمكننا إضافة $($ $v$ $,$ $u$ $)$ إلى $E$ ثم تعيين $c$ $($ $v$ $,$ $u$ $) = 0$ .

إذا تم تمييز عقدتين في $G$ - إحداهما كمصدر $s$ والأخرى كمصب $t$ - فإن $(G ، c ، s ، t)$ تسمى شبكة تدفق . ^{[ 1 ]}

التدفقات

تُستخدم دوال التدفق لنمذجة صافي تدفق الوحدات بين أزواج من العقد، وهي مفيدة عند طرح أسئلة مثل: ما هو الحد الأقصى لعدد الوحدات التي يمكن نقلها من عقدة المصدر s إلى عقدة المصب t؟ ويُستخدم مقدار التدفق بين عقدتين لتمثيل صافي كمية الوحدات المنقولة من عقدة إلى أخرى.

تمثل دالة الفائض $x f : V \to ℝ$ صافي التدفق الداخل إلى عقدة معينة $u$ (أي مجموع التدفقات الداخلة إلى u $)$ ويتم تعريفها بواسطة $x_{f}(u)=\sum _{w\in V}f(w,u)-\sum _{w\in V}f(u,w).$ يُقال إن العقدة $u$ نشطة إذا كانت $x f (u) > 0$ (أي أن العقدة $u$ تستهلك التدفق)، أو ناقصة إذا كانت $x f (u) < 0$ (أي أن العقدة $u$ تُنتج التدفق)، أو حافظة إذا كانت $x f (u) = 0.$ في شبكات التدفق، يكون المصدر $s$ ناقصًا، والمصب $t$ نشطًا. تُعد التدفقات الزائفة والتدفقات الممكنة والتدفقات الأولية أمثلة على دوال التدفق.

التدفق الزائف هو دالة

f

لكل حافة في الشبكة والتي تحقق القيدين التاليين لجميع العقد

u

و

v

:

قيد التناظر المائل : التدفق على قوس من $u$ إلى $v$ يكافئ نفي التدفق على قوس من $v$ إلى $u$ ، أي: $f (u, v) = -f (v, u)$ . تشير إشارة التدفق إلى اتجاهه.
قيد السعة : لا يمكن أن يتجاوز تدفق القوس سعته، أي: $f (u, v) \leq c (u, v)$ .

التدفق المسبق هو تدفق زائف، بالنسبة لجميع

v ∈ V \{ s }

، يحقق القيد الإضافي التالي:

التدفقات غير الناقصة : يكون صافي التدفق الداخل إلى العقدة $v$ غير سالب، باستثناء المصدر الذي "ينتج" التدفق. أي: $x f (v) \geq 0$ لجميع $v ∈ V \{ s }$ .

التدفق الممكن ، أو مجرد التدفق ، هو تدفق زائف يحقق القيد الإضافي التالي لجميع

قيم v ∈ V \{ s , t } :

قيد حفظ التدفق : يكون صافي التدفق الكلي الداخل إلى العقدة $v$ مساويًا للصفر لجميع العقد في الشبكة باستثناء المصدر $s$ والمصب $t$ ، أي: $x f (v) = 0$ لجميع $v ∈ V \{ s , t }$ . بعبارة أخرى، بالنسبة لجميع العقد في الشبكة باستثناء المصدر $s$ والمصب $t$ ، فإن المجموع الكلي للتدفق الوارد إلى العقدة يساوي تدفقها الخارج (أي $\sum _{(u,v)\in E}f(u,v)=\sum _{(v,z)\in E}f(v,z)$ ، لكل رأس $v ∈ V \{ s , t }$ ).

قيمة التدفق الممكن $f في الشبكة$ $،$ $|$ $f$ $|$ $، هي صافي التدفق$ إلى المصب $t$ في الشبكة، أي: $|f| = xf(t). لاحظ أن قيمة التدفق في الشبكة تساوي أيضًا إجمالي التدفق الخارج من المصدر s، أي: |f| = -xf$ $($ $s$ $)$ $.$ $كذلك$ ، $إذا$ $عرّفنا$ A $كمجموعة$ من $العقد$ $في$ $G$ $بحيث$ $s$ $\in$ $A$ $و$ t $\notin$ A $،$ فإن $قيمة$ $التدفق$ $تساوي$ إجمالي $صافي$ $التدفق$ $الخارج$ $من$ A (أي $|$ $f$ $|$ $=$ $fout$ $($ $A$ $)$ $-$ $fin$ $($ $A$ $)$ $)$ . ^[²^] $قيمة$ التدفق في الشبكة هي إجمالي كمية التدفق من $s$ إلى $t$ .

مفاهيم مفيدة لحل مشاكل التدفق

تحلل التدفق

يُعدّ تحليل التدفق ^{[ 3 ]} عمليةً لتقسيم تدفقٍ مُعطى إلى مجموعةٍ من تدفقات المسارات وتدفقات الدورات. يُمكن تحليل أي تدفقٍ عبر شبكةٍ إلى مسارٍ واحدٍ أو أكثر، وما يُقابله من كميات، بحيث يُساوي كل ضلعٍ في التدفق مجموع كميات جميع المسارات التي تمر عبره. يُعدّ تحليل التدفق أداةً فعّالةً في مسائل التحسين لزيادة أو تقليل مُعاملات تدفقٍ مُحددة.

إضافة الأقواس والتدفقات

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

بالنظر إلى أي عقدتين $u$ و $v$ ، فإن وجود قوسين من $u$ إلى $v$ بسعات $c 1 (u,v)$ و $c 2 (u,v)$ على التوالي يعادل النظر في قوس واحد فقط من $u$ إلى $v$ بسعة تساوي $c 1 (u,v)+ c 2 (u,v)$ .
بالنظر إلى أي عقدتين $u$ و $v$ ، فإن وجود قوسين من $u$ إلى $v$ مع تدفقات زائفة $f 1 (u,v)$ و $f 2 (u,v)$ على التوالي يعادل النظر في قوس واحد فقط من $u$ إلى $v$ مع تدفق زائف يساوي $f 1 (u,v)+ f 2 (u,v)$ .

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

المتبقيات

تُرمز السعة المتبقية لقوس $e$ بالنسبة لتدفق وهمي $f بالرمز$ $c f$ ، وهي الفرق بين سعة القوس وتدفقه. أي أن $c f (e) = c (e) - f (e)$ . ومن هذا، يمكننا إنشاء شبكة متبقية ، يُرمز لها بـ $G f (V, E f)$ ، بدالة سعة $c f$ تُنمذج مقدار السعة المتاحة على مجموعة الأقواس في $G = (V, E)$ . وبشكل أكثر تحديدًا، تُمثل دالة السعة $c f$ لكل قوس $(u, v)$ في الشبكة المتبقية مقدار التدفق الذي يمكن نقله من $u$ إلى $v$ بالنظر إلى الحالة الراهنة للتدفق داخل الشبكة.

يُستخدم هذا المفهوم في خوارزمية فورد-فولكرسون التي تحسب الحد الأقصى للتدفق في شبكة التدفق.

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

مسارات معززة

المسار المُعزِّز هو مسار $(u1, u2, ..., uk)$ في الشبكة المتبقية، حيث $u1 = s و uk$ $= t ،$ ولكل ui $و$ $ui$ $+$ $1، يكون$ $($ $cf$ $($ $ui$ $,$ $ui$ $+$ $1$ $)$ $>$ $0$ $) ( 1 \leq$ $i$ $< k )$ . بعبارة أخرى، المسار المُعزِّز هو مسار تدفق متاح من المصدر إلى المصب. تكون الشبكة في أقصى تدفق لها $إذا$ وفقط إذا لم يكن هناك مسار مُعزِّز في $الشبكة$ المتبقية $Gf .$

تُعرَّف نقطة الاختناق بأنها الحد الأدنى للسعة المتبقية لجميع الحواف في مسار التوسيع المُعطى. ^{[ 2 ]} انظر المثال الموضح في قسم "الأمثلة" من هذه المقالة. تكون شبكة التدفق في أقصى تدفق لها إذا وفقط إذا كان لديها نقطة اختناق بقيمة تساوي صفرًا. إذا وُجد أي مسار توسيع، فسيكون وزن نقطة الاختناق فيه أكبر من صفر. بعبارة أخرى، إذا كانت قيمة نقطة الاختناق أكبر من صفر، فهذا يعني وجود مسار توسيع من المصدر إلى المصب. مع ذلك، نعلم أنه في حال وجود أي مسار توسيع، فإن الشبكة لا تكون في أقصى تدفق لها، مما يعني بدوره أنه إذا كانت قيمة نقطة الاختناق أكبر من صفر، فإن الشبكة لا تكون في أقصى تدفق لها.

يشير مصطلح "زيادة التدفق" في مسار التوسيع إلى تحديث التدفق $(f)$ لكل قوس في هذا المسار ليُساوي سعة $(c)$ نقطة الاختناق. وتُقابل زيادة التدفق دفع تدفق إضافي على طول مسار التوسيع حتى لا يتبقى أي سعة متبقية متاحة في نقطة الاختناق.

مصادر و/أو مصارف متعددة

أحيانًا، عند نمذجة شبكة تحتوي على أكثر من مصدر، يُضاف مصدر رئيسي إلى الرسم البياني. ^{[ 4 ]} يتكون هذا المصدر من رأس متصل بكل مصدر من المصادر بحواف ذات سعة غير محدودة، ليعمل كمصدر شامل. ويُطلق على بنية مماثلة للمصارف اسم المصرف الرئيسي . ^{[ 5 ]}

مثال

في الشكل 1، ترى شبكة تدفق بمصدر مُسمى $s$ ، ومصب $t$ ، وأربع عقد إضافية. يُشار إلى التدفق والسعة بـ $f/c$ لاحظ كيف تحافظ الشبكة على قيد السعة وقيد حفظ التدفق. يبلغ إجمالي التدفق من النقطة $s$ إلى $النقطة t$ خمسة، وهو ما يتضح بسهولة من حقيقة أن إجمالي التدفق الخارج من $s$ هو خمسة، وهو نفسه التدفق الداخل إلى $t$ . وبحسب قيد التناظر المائل، فإن التدفق من $c$ إلى $a$ يساوي -2 لأن التدفق من $a$ إلى $c$ يساوي 2.

في الشكل 2، يمكنك رؤية الشبكة المتبقية لنفس التدفق المحدد. لاحظ وجود سعة متبقية موجبة على بعض الحواف حيث تكون السعة الأصلية صفرًا في الشكل 1، على سبيل المثال للحافة $(d,c)$ هذه الشبكة ليست في أقصى طاقتها الاستيعابية . هناك سعة متاحة على طول المسارات . $(s,a,c,t)$ ، $(s,a,b,d,t)$ و $(s,a,b,d,c,t)$ والتي تمثل مسارات التضخيم.

عنق الزجاجة $(s,a,c,t)$ المسار يساوي $\min(c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t))$ $=\min(c_{f}(s,a),c_{f}(a,c),c_{f}(c,t))$ $=\min(5-3,3-2,2-1)$ $=\min(2,1,1)=1$ .

التطبيقات

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

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

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

مشاكل تصنيف التدفق

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

خوارزميات معروفة لحل مشكلة التدفق الأقصى
المخترع(ون)	سنة	التعقيد الزمني (مع $n$ عقدة و $m$ قوس)
خوارزمية دينيك	1970	$O (mn 2)$
خوارزمية إدموندز-كارب	1972	$O (m 2 n)$
خوارزمية MPM (مالهوترا، برامود كومار، وماهيشواري) ^{[ 6 ]}	1978	$O (n 3)$
خوارزمية الدفع وإعادة التسمية ( غولدبيرغ وتارجان )	1988	$O (n 2 m)$
جيمس ب. أورلين ^{[ 7 ]}	2013	$O (mn)$
لي تشن، راسموس كينغ، يانغ بي ليو، ريتشارد بينج، ماكسيميليان بروبست جوتنبرج، سوشانت ساشديفا	2022	$O(m^{1+o(1)})$

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

في مسألة تدفق التكلفة الدنيا ، كل حافة $u,v$ له تكلفة محددة $k(u,v)$ وتكلفة إرسال التدفق $f(u,v)$ على طول الحافة $f(u,v)\cdot k(u,v)$ الهدف هو إرسال كمية معينة من التدفق من المصدر إلى المصب، بأقل سعر ممكن.

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

في مسألة الدوران ، يكون لديك حد أدنى $\ell (u,v)$ على الحواف، بالإضافة إلى الحد الأعلى $c(u,v)$ لكل حافة تكلفة أيضًا. غالبًا ما ينطبق مبدأ حفظ التدفق على جميع العقد في مسألة الدوران، وهناك اتصال من المصب إلى المصدر. بهذه الطريقة، يمكنك تحديد التدفق الكلي باستخدام $\ell (t,s)$ و $c(t,s)$ . يدور التدفق عبر الشبكة، ومن هنا جاء اسم المشكلة.

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

في مسألة تحديد مصدر المعلومات ، تحاول الخوارزمية تحديد عقدة المصدر الأكثر احتمالاً لانتشار المعلومات عبر شبكة مُراقبة جزئياً. يمكن إنجاز ذلك في زمن خطي للأشجار وزمن مكعب للشبكات العشوائية، ولها تطبيقات تتراوح من تتبع مستخدمي الهواتف المحمولة إلى تحديد المصدر الأصلي لتفشي الأمراض. ^{[ 8 ]}

انظر أيضاً

مراجع

↑ AV Goldberg، É. Tardos و RE Tarjan، خوارزميات تدفق الشبكة، تقرير فني STAN-CS-89-1252، قسم علوم الحاسوب بجامعة ستانفورد، 1989
1 2 كلاينبرج، جون (2011). تصميم الخوارزمية . إيفا تاردوس ( الطبعة الثانية). بوسطن، ماساتشوستس: أديسون ويسلي. ص 342، 346. ردمك 978-0-13-213108-7. OCLC 796210667 .
↑ أهوجا، رافيندرا ك.؛ ماجنانتي، توماس ل.؛ أورلين، جيمس ب. (1993). تدفقات الشبكة: النظرية والخوارزميات والتطبيقات . إنجلوود كليفس (نيوجيرسي): برنتيس هول. ISBN 978-0-13-617549-0.
↑ تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "المصدر الفائق" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .
↑ تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "Supersink" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .
↑ مالهوترا، في إم؛ كومار، إم. برامود؛ ماهيشواري، إس إن (1978). "أن $O(|V|^{3})$ خوارزمية لإيجاد أقصى تدفقات في الشبكات (ملف PDF) . رسائل معالجة المعلومات . 7 (6): 277-278 . doi : 10.1016/0020-0190(78)90016-9 . مؤرشف (ملف PDF) من الأصل بتاريخ 18 أبريل 2021. تم الاطلاع عليه بتاريخ 11 يوليو 2019 .
↑ أورلين، جيمس ب. (2013-06-01). "أقصى تدفقات في زمن O(nm) أو أفضل" . وقائع الندوة السنوية الخامسة والأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '13. بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 765-774 . doi : 10.1145/2488608.2488705 . hdl : 1721.1/88020 . ISBN 978-1-4503-2029-0. S2CID 207205207 .
↑ بينتو، بي سي؛ ثيران، بي؛ فيترلي، إم. (2012). "تحديد مصدر الانتشار في الشبكات واسعة النطاق" ( ملف PDF) . مجلة Physical Review Letters . 109 (6) 068702. arXiv : 1208.2534 . Bibcode : 2012PhRvL.109f8702P . doi : 10.1103/PhysRevLett.109.068702 . PMID 23006310. S2CID 14526887. مؤرشف (PDF) من النسخة الأصلية بتاريخ 22 أكتوبر 2012. تاريخ الاسترجاع: 14 أغسطس 2012 .

للمزيد من القراءة

جورج ت. هاينمان؛ غاري بوليس؛ ستانلي سيلكو (2008). "الفصل 8: خوارزميات تدفق الشبكة". الخوارزميات باختصار . دار نشر أورايلي ميديا . الصفحات 226-250 . ISBN 978-0-596-51624-6.
رافيندرا ك. أهوجا ؛ توماس ل. ماجنانتي ؛ جيمس ب. أورلين (1993). تدفقات الشبكات: النظرية والخوارزميات والتطبيقات . برنتيس هول. ISBN 0-13-617549-X.
بولوباس، بيلا (1979). نظرية الرسم البياني: دورة تمهيدية . هايدلبرغ: سبرينغر-فيرلاغ. ISBN 3-540-90399-2.
شارتراند، غاري ؛ أويلرمان، أورترود ر. (1993). نظرية الرسم البياني التطبيقية والخوارزمية . نيويورك: ماكجرو هيل. ISBN 0-07-557101-3.
إيفن، شيمون (1979). خوارزميات الرسوم البيانية . روكفيل، ماريلاند: مطبعة علوم الحاسوب. ISBN 0-914894-21-8.
جيبونز، آلان (1985). نظرية الرسم البياني الخوارزمية . كامبريدج: مطبعة جامعة كامبريدج. ISBN 0-521-28881-9.
توماس هـ. كورمن ؛ تشارلز إي. ليسرسون ؛ رونالد ل. ريفست ؛ كليفورد شتاين (2001) [1990]. "26". مقدمة في الخوارزميات (الطبعة الثانية ). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 696-697 . ISBN 0-262-03293-7.

روابط خارجية

مشكلة التدفق الأقصى
أمثلة حقيقية للرسوم البيانية
مكتبة Lemon C++ التي تحتوي على العديد من خوارزميات التدفق الأقصى والتكلفة الأدنى للتداول
تم أرشفة QuickGraph في 21 يناير 2018 على موقع Wayback Machine ، وهو عبارة عن هياكل بيانات وخوارزميات رسومية لـ .Net

[1] AV Goldberg، É. Tardos و RE Tarjan، خوارزميات تدفق الشبكة، تقرير فني STAN-CS-89-1252، قسم علوم الحاسوب بجامعة ستانفورد، 1989

[:0-2] 1 2 كلاينبرج، جون (2011). تصميم الخوارزمية . إيفا تاردوس ( الطبعة الثانية). بوسطن، ماساتشوستس: أديسون ويسلي. ص 342، 346. ردمك 978-0-13-213108-7. OCLC 796210667 .

[3] أهوجا، رافيندرا ك.؛ ماجنانتي، توماس ل.؛ أورلين، جيمس ب. (1993). تدفقات الشبكة: النظرية والخوارزميات والتطبيقات . إنجلوود كليفس (نيوجيرسي): برنتيس هول. ISBN 978-0-13-617549-0.

[4] تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "المصدر الفائق" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .

[5] تتضمن هذه المقالة موادًا متاحة للعموم من بول إي. بلاك. "Supersink" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني للمعايير والتكنولوجيا (NIST) .

[6] مالهوترا، في إم؛ كومار، إم. برامود؛ ماهيشواري، إس إن (1978). "أن $O(|V|^{3})$ خوارزمية لإيجاد أقصى تدفقات في الشبكات (ملف PDF) . رسائل معالجة المعلومات . 7 (6): 277-278 . doi : 10.1016/0020-0190(78)90016-9 . مؤرشف (ملف PDF) من الأصل بتاريخ 18 أبريل 2021. تم الاطلاع عليه بتاريخ 11 يوليو 2019 .

[7] أورلين، جيمس ب. (2013-06-01). "أقصى تدفقات في زمن O(nm) أو أفضل" . وقائع الندوة السنوية الخامسة والأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '13. بالو ألتو، كاليفورنيا، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 765-774 . doi : 10.1145/2488608.2488705 . hdl : 1721.1/88020 . ISBN 978-1-4503-2029-0. S2CID 207205207 .

[8] بينتو، بي سي؛ ثيران، بي؛ فيترلي، إم. (2012). "تحديد مصدر الانتشار في الشبكات واسعة النطاق" ( ملف PDF) . مجلة Physical Review Letters . 109 (6) 068702. arXiv : 1208.2534 . Bibcode : 2012PhRvL.109f8702P . doi : 10.1103/PhysRevLett.109.068702 . PMID 23006310. S2CID 14526887. مؤرشف (PDF) من النسخة الأصلية بتاريخ 22 أكتوبر 2012. تاريخ الاسترجاع: 14 أغسطس 2012 .

[ 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗