TD 4: Théorie des graphes – Mathématiques

يحتوي هذا المستند على سلسلة تمارين موجهة (TD) رقم 4 في مادة نظرية الرسوم البيانية للعام الجامعي 2023/2024. يركز على مفهوم flot (التدفق) في الشبكات الموجهة، ويقدم تمارين تطبيقية لتقييم ما إذا كان flot معينًا maximalًا أم لا، وكيفية تحسينه باستخدام السلاسل المحسنة. يتناول التمرين الأول إثبات عدم maximalité flot المعطى، ثم تحسينه عبر سلسلة محسنة محددة، وأخيرًا تحديد عدد flotsmaximaux الممكنة وقيمتها. يوضح التمرين الثاني تطبيق خوارزمية Ford-Fulkerson خطوة بخطوة على شبكة معقدة، مع إظهار كيفية الوصول إلى flot maximal واستخدام نظرية القطع-الفلوت لتبرير maximalité. أما التمرين الثالث فيعالج مشكلة مصادر ومتعددة puits من خلال إضافة super-source و super-sink، ثم تطبيق الخوارزمية لتحديد أقصى flot الممكن وتقييم ما إذا كان يمكن满足 احتياجات القرى، مع دراسة تأثير زيادة سعة أحد الأقواس على النتيجة. يربط المستند بين المفاهيم النظرية مثل السلاسل المحسنة، القطع الأدنى، ونظرية maximalité، والتطبيقات العملية في شبكات التوزيع، مما يعزز فهم الطالب لخوارزميات تحسين الشبكات ويعدّه لحل مشكلات مشابهة في الامتحانات أو المشاريع الهندسية.