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

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

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

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

قراءة المقال الكامل على ويكيبيديا ←