أساسيات المخططات والاتصالية
تقدم أساسيات نظرية المخططات المخططات، ومعاملاتها الأساسية، ومفاهيم الاتصالية والتجوال التي تصف كيفية ترابط المخطط.
Definition
يتكون المخطط من مجموعة من الرؤوس ومجموعة من الحواف التي تربط أزواجًا من الرؤوس؛ وتقيس الاتصالية مدى بقاء المخطط قطعة واحدة عند إزالة الرؤوس أو الحواف.
Scope
يغطي هذا الموضوع تعريفات المخططات والمخططات الموجهة، والدرجة ومبرهنة المصافحة، والمخططات الفرعية والتماثل، والمشيات، والمسارات والدورات، والاتصالية والمكونات، والتوصيفات الكلاسيكية للمخططات الأويلرية والهاملتونية. ويؤسس للمفردات والنتائج الهيكلية الأساسية المستخدمة في جميع أنحاء نظرية المخططات.
Core questions
- ما هي المعاملات الأساسية - الرتبة والحجم والدرجة - للمخطط؟
- متى يكون المخطط متصلاً، وما مدى قوة اتصاليته ضد الحذف؟
- متى يسمح المخطط بمشية مغلقة تستخدم كل حافة مرة واحدة بالضبط؟
- كيف تقوم المسارات والدورات بترميز إمكانية الوصول والهيكل؟
Key concepts
- الرؤوس، الحواف، والدرجة
- المشيات، المسارات، والدورات
- المكونات المتصلة
- اتصالية الرؤوس والحواف
- الدوائر الأويلرية
- الدورات الهاملتونية
Key theories
- مبرهنة المصافحة
- في أي مخطط، يساوي مجموع درجات جميع الرؤوس ضعف عدد الحواف، مما يعني فورًا أن عدد الرؤوس ذات الدرجة الفردية هو عدد زوجي.
- مبرهنة أويلر حول الدوائر الأويلرية
- يحتوي المخطط المتصل على مشية مغلقة تعبر كل حافة مرة واحدة بالضبط إذا وفقط إذا كانت كل رأس ذات درجة زوجية، وهي النتيجة التي تقوم عليها حل أويلر لمشكلة جسور كونيغسبرغ.
Clinical relevance
يعد تحليل الاتصالية محوريًا لموثوقية الشبكة، والتوجيه، وتصميم أنظمة الاتصالات والنقل المتسامحة مع الأخطاء، بينما تنشأ الهياكل الأويلرية والهاملتونية في مشاكل التوجيه والتسلسل.
History
قدمت ورقة أويلر عام 1736 حول جسور كونيغسبرغ مفهوم تجوال المخططات؛ وقدمت مبرهنة منغر عام 1927 الازدواجية الأساسية بين الاتصالية والمسارات المنفصلة التي ترتكز عليها النظرية الحديثة.
Key figures
- Leonhard Euler
- Karl Menger
Related topics
Seminal works
- diestel2017
Frequently asked questions
- ما الفرق بين الدورة الأويلرية والدورة الهاملتونية؟
- تستخدم الدورة الأويلرية كل حافة مرة واحدة بالضبط، بينما تزور الدورة الهاملتونية كل رأس مرة واحدة بالضبط؛ الأولى لها توصيف بسيط للدرجة، لكن تحديد الثانية صعب حسابيًا.
- ماذا يعني أن يكون المخطط متصلاً k؟
- يكون المخطط متصلاً k إذا ظل متصلاً كلما تمت إزالة أقل من k من الرؤوس، مما يحدد مرونته تجاه أعطال الرؤوس.