تدفقات الشبكة
تنظيم صفحاتك في مجموعات
يمكنك حفظ المحتوى وتصنيفه حسب إعداداتك المفضّلة.
يمكن تمثيل العديد من المشكلات في علوم الكمبيوتر من خلال رسم بياني يتكون
من عُقد وروابط بينها. ومن الأمثلة على ذلك مشكلات تدفق الشبكة، والتي تتضمن
نقل البضائع أو المواد عبر شبكة، مثل نظام السكك الحديدية.
يمكنك تمثيل تدفق الشبكة من خلال رسم بياني تكون عُقده مدنًا وأقواسها هي خطوط السكك الحديدية بينها. (تُسمى التدفقات لأن خصائصها مشابهة لخصائص المياه التي تتدفق من خلال شبكة من الأنابيب).
يتمثل القيد الرئيسي في تدفقات الشبكة في أن لكل قوس سعة — وهو أقصى مبلغ يمكن نقله عبر القوس في فترة زمنية ثابتة.
تكمن مشكلة الحد الأقصى في التدفق في تحديد الحد الأقصى للمبلغ الإجمالي الذي يمكن نقله عبر جميع الأقواس في الشبكة، وذلك وفقًا
لقيود السعة.
كان أول عالم يدرس هذه المشكلة هو عالم الرياضيات الروسي "آي إن تولستوي" في ثلاثينيات القرن العشرين. توضح الخريطة أدناه شبكة السكك الحديدية
الفعلية التي أراد العثور على أقصى تدفق لها.
توفر "أدوات OR" عدة أدوات حل لمشكلات تدفق الشبكة في مكتبات الرسم البياني التابعة لها.
تقدم الأقسام التالية أمثلة لمشكلات تدفق الشبكة وتوضّح كيفية حلها:
إنّ محتوى هذه الصفحة مرخّص بموجب ترخيص Creative Commons Attribution 4.0 ما لم يُنصّ على خلاف ذلك، ونماذج الرموز مرخّصة بموجب ترخيص Apache 2.0. للاطّلاع على التفاصيل، يُرجى مراجعة سياسات موقع Google Developers. إنّ Java هي علامة تجارية مسجَّلة لشركة Oracle و/أو شركائها التابعين.
تاريخ التعديل الأخير: 2024-08-09 (حسب التوقيت العالمي المتفَّق عليه)
[null,null,["تاريخ التعديل الأخير: 2024-08-09 (حسب التوقيت العالمي المتفَّق عليه)"],[[["\u003cp\u003eNetwork flow problems, like transporting goods across a railway system, can be represented by graphs with nodes and links, where links have capacity limits.\u003c/p\u003e\n"],["\u003cp\u003eThe maximum flow problem aims to find the maximum transportable amount across a network, respecting capacity constraints.\u003c/p\u003e\n"],["\u003cp\u003eOR-Tools offers various solvers in its graph libraries to address network flow problems like maximum flows and minimum cost flows.\u003c/p\u003e\n"],["\u003cp\u003eExample applications of network flows include assignments with individual workers or teams, solvable using OR-Tools.\u003c/p\u003e\n"]]],["Computer science utilizes graphs to model problems like network flow, where goods are transported across a network (e.g., railway). Each link (arc) in the network has a capacity, limiting transport volume. The maximum flow problem determines the highest total transport volume across all arcs, respecting these capacity constraints. This problem, first studied by A.N. Tolstoi, can be solved using solvers from the OR-Tools graph libraries, which are useful for problems such as maximum flows, minimum cost flows, and assignment problems.\n"],null,["# Network Flows\n\nMany problems in computer science can be represented by a graph consisting of\nnodes and links between them. Examples are **network flow** problems, which\ninvolve transporting goods or material across a network, such as a railway system.\n\nYou can represent a network flow by a graph whose nodes are cities and whose\narcs are rail lines between them. (They're called **flows** because their\nproperties are similar to those of water flowing through a network of pipes.)\n\nA key constraint in network flows is that each arc has a **capacity** ---\nthe maximum amount that can be transported across the arc in a fixed period of\ntime.\n\nThe **maximum flow problem** is to determine the maximum total amount that can\nbe transported across all arcs in the network, subject to the capacity\nconstraints.\n\nThe first person to study this problem was the Russian mathematician A.N.\nTolstoi, in the 1930s. The map below shows the actual railway network for which\nhe wanted to find a maximum flow.\n\nOR-Tools provides several solvers for network flow problems in its\n[graph](/optimization/reference/graph) libraries.\n\nThe following sections present examples of network flow problems and show how to\nsolve them:\n\n- [Maximum Flows](/optimization/flow/maxflow)\n- [Minimum Cost Flows](/optimization/flow/mincostflow)\n- [Assignment as a Minimum Cost Flows](/optimization/flow/assignment_min_cost_flow#example)\n- [Assignment with Teams of Workers](/optimization/flow/assignment_min_cost_flow#teams-workers)"]]
