TD 2: التعريفات الأساسية – نظرية الرسوم البيانية – Théorie des graphes

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