Chapitre II : Isomorphisme, graphe planaire, graphe eulérien et graphe hamiltonien – Théorie des graphes

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

بعد ذلك يعالج الفصل مفهوم الرسم البياني المستوي (Graphe planaire)، وهو الرسم الذي يمكن تمثيله على مستوى دون تقاطع الحواف. يقدم الدرس أمثلة تطبيقية، مثل دراسة قابلية رسم الرسم الكامل K4، كما يعرض مبرهنة كوراتوفسكي التي تحدد الرسوم غير المستوية اعتمادا على وجود رسم جزئي مماثل لـ K5 أو K3,3. كما يتم تعريف عملية التقسيم (Subdivision) التي تعتمد على استبدال الحواف بسلاسل من الحواف.

ينتقل الفصل إلى الرسوم الأويلرية (Graphes eulériens) انطلاقا من مشكلة جسور كونيغسبرغ التي حلها أويلر سنة 1736. يشرح مفهوم الدورة والمسار الأويلريين، ويعرض مبرهنة أويلر التي تربط وجود دورة أويلرية باتصال الرسم ودرجات الرؤوس. كما يميز بين الرسم الأويلري والرسم شبه الأويلري.

في الجزء الأخير يتم تقديم مفهوم الرسم الهاملتوني (Graphe hamiltonien) الذي يعتمد على وجود دورة تمر عبر جميع الرؤوس مرة واحدة. يشكل هذا الفصل أساسا مهما لحل مسائل تصنيف الرسوم، التحقق من الخصائص البنيوية، والاستعداد للتمارين والاختبارات في مقياس نظرية الرسوم.