TD 3: نظرية الرسوم البيانية – علم الحاسوب

تقدم هذه الوثيقة (TD 3) لمادة نظرية الرسوم البيانية مستوى الليسانس الثانية (L2) للعام الجامعي 2023/2024 ملخصاً شاملاً للمفاهيم الأساسية في نظرية الرسوم البيانية مع تمارين تطبيقية وحلولها. تبدأ الوثيقة بتعريف الرسم البياني المسطح وشروط خطته وفقًا لنظرية كوراتوفسكي التي تنص على أن الرسم البياني مسطح إذا ولم يحتوي على رسم فرعي منزليomorf إلى K3,3 أو K5. ثم تُذكر صيغة أويلر للرسم البياني المتصل المسطح: n - m + f = 2، وتظهر نتيجة أن كل رسم مسطح بسيط يحتوي على قمة بدرجة لا تزيد عن خمسة. بعد ذلك تنتقل الوثيقة إلى الرسوم أويلرية وهاميلتونية، حيث تُعرّف الرسم البياني أويلري بأنه متصل وكل درجاته زوجية (في الحالة غير الموجهة) أو يساوي الدرجة الداخلة والخارجة (في الحالة الموجهة)، وتذكر نظريات مينييل، ديارك وأور لوجود دورة هاميلتونية تحت شروط درجات معينة. كما تتناول الوثيقة خاصية الأشجار: وجود至少两个 قمة pendant، وشرط أن يكون الرسم البياني متصلاً ليحتوي على شجرة جزئية. أخيراً تُناقش التلوين، مع التذكير بأن كل رسم مسطح يمكن تلوينه بألون أربعة على الأكثر، وعلاقة عددchromatic بالحد الأقصى للدرجة وحجم أكبر كليك. تُرفق الوثيقة بأربع تمارين مفصلة مع حلول خطوة بخطوة تُظهر كيفية تطبيق هذه المفاهيم على مشاكل عملية مثل تمثيل شبكات التجسس، تخطيط طاولة دائرية، إيجاد أقصر مسار في شبكة توجيهية، وتحليل المكونات fortement connexes في رسمOriented. تساعد هذه التمارين الطالب على ربط النظرية بالتطبيق وتعزيز مهارات التحليل والحساب في سياق مادة الرسوم البيانية.