Examen Final : Problèmes classiques de théorie des graphes – Théorie des graphes

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

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

يعالج التمرين الثالث شبكة نقل موجهة تحتوي على تدفقات وسعات، حيث يطلب حساب قيمة التدفق الحالي والتحقق من خصائصه مثل التوافق والمحافظة والاكتمال، ثم تطبيق خوارزمية Ford-Fulkerson لإيجاد التدفق الأقصى وتحديد الأقواس التي يمكن زيادة سعتها لتحسين الأداء.

أما التمرين الرابع فيتناول إيجاد أسرع المسارات بين المدن في شبكة نقل جوي، وهي مسألة أقصر المسارات في الرسوم البيانية الموزونة، مع الاعتماد على خوارزمية مناسبة مثل خوارزمية Dijkstra.

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