TD 4: Flot maximal et algorithme de Ford-Fulkerson – Théorie des graphes

يهدف هذا TD إلى تعزيز فهم طلبة السنة الثانية في informatique لمفاهيم نظرية الشبكات والتدفق الأقصى. يبدأ التمرين الأول بتحليل flot donné وإثبات عدم maximalité، ثم طلب تحسينه باستخدام مسار محسن وتحديد عدد التدفقات ذات القيمة القصوى الممكنة. يتناول التمرين الثاني تطبيق خوارزمية فورد-فولكرسون خطوة بخطوة، مع تحسين flot عبر سلاسل محسنة متتالية، وأخيراً إثبات maximalité باستخدام نظرية القص الأدنى التي تم دراستها في المحاضرة. أما التمرين الثالث فيشكل مشكلة توزيع مياه من ثلاث خزانات إلى أربع قرى، حيث يُطلب بناء شبكة تدفق تمثل القدرات علىarcs والطلب على القرى، ثم تطبيق الخوارزمية للعثور على أقصى قيمة flot وتحقق ما إذا يمكن تلبية جميع الطلبات، ثم تعديل سعة أحد arcs وإعادة تشغيل الخوارزمية من flot السابق. من خلال هذه التمارين، يتدرب الطالب على تمثيل المشكلات كشبكات تدفق، تحديد السعة المتبقية، بناء الرسم المتبقي، إيجاد مسار محسن، وتحديث flot حتى الوصول إلى الحالة المثلى. كما يربط التمرين بين النظرية والتطبيق العملي، مما يعزز القدرة على حل مشكلات تحسين الشبكات في سياقات حقيقية مثل توزيع الموارد، الشبكات الاتصالية، واللوجستيك.