الأعمال الموجهة TD 3: الرسوم البيانية المستوية والأويلرية والهاملتونية والأشجار والتلوين – نظرية الرسوم البيانية – Théorie des graphes

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