Corrigé type de l’examen session normale : Théorie des graphes – Informatique

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

يعالج التصحيح كذلك خاصية الأشجار، مع البرهنة على أن متوسط درجات رؤوس أي شجرة أصغر من 2 بالاعتماد على مبرهنة الأيدي المصافحة والعلاقة بين عدد الرؤوس وعدد الحواف في الشجرة. كما يقدم تطبيقًا على تلوين الرسوم البيانية باستعمال خوارزمية Welsh-Powell، مع ترتيب الرؤوس حسب درجاتها وتعيين الألوان ثم التحقق من أن عدد الألوان المستعملة أمثل.

يتضمن الجزء الأخير برنامجًا بلغة C++ يطبق خوارزمية البحث بعرض الرسم البياني (BFS) انطلاقًا من رأس محدد، باستعمال مصفوفة التجاور وقائمة التجاور وطابور لمعالجة الرؤوس. يوضح البرنامج كيفية زيارة الرؤوس واختبار اتصال الرسم البياني.

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