الأشجار والهياكل الشاملة
الشجرة هي رسم بياني متصل لا دوري، وتستخلص الهياكل الشاملة هذه الهياكل العظمية المتصلة الدنيا من الرسوم البيانية الأكبر.
Definition
الشجرة هي رسم بياني متصل لا يحتوي على دورات؛ الشجرة الشاملة لرسم بياني متصل هي رسم بياني فرعي يكون شجرة ويتضمن كل رأس من رؤوس الرسم البياني.
Scope
يغطي هذا الموضوع التوصيفات المتكافئة للأشجار، والأشجار الجذرية والموسومة، والأشجار والغابات الشاملة، وتعدادها من خلال صيغة كايلي ونظرية مصفوفة الشجرة. كما يقدم الأشجار الشاملة الدنيا كمشكلة تحسين، ويربط نظرية الرسم البياني بتصميم الخوارزميات والتعداد التوافقي.
Core questions
- ما هي الشروط المتكافئة التي تميز الرسم البياني كشجرة؟
- كم عدد الأشجار الموسومة الموجودة على عدد معين من الرؤوس؟
- كم عدد الأشجار الشاملة التي يحتويها رسم بياني معين؟
- كيف يمكن إيجاد شجرة شاملة ذات وزن إجمالي أدنى بكفاءة؟
Key concepts
- الرسوم البيانية المتصلة اللا دورية
- الأشجار الجذرية والموسومة
- الأشجار والغابات الشاملة
- متتاليات بروفر
- صيغة كايلي
- الشجرة الشاملة الدنيا
Key theories
- صيغة كايلي
- يوجد بالضبط n^(n-2) شجرة موسومة مميزة على n رأسًا، وهي نتيجة تعداد كلاسيكية يمكن إثباتها بواسطة متتاليات بروفر، أو نظرية مصفوفة الشجرة، أو العديد من التقابلات الأنيقة.
- نظرية مصفوفة الشجرة
- يساوي عدد الأشجار الشاملة لرسم بياني أي عامل مرافق لمصفوفة لابلاس الخاصة به، مما يربط العد التوافقي للأشجار الشاملة بالجبر الخطي والمحددات.
Clinical relevance
تكمن الأشجار الشاملة في أساس تصميم الشبكات وتوجيه البث، وتحل الأشجار الشاملة الدنيا مشاكل الاتصال الأقل تكلفة، وتنظم هياكل الأشجار البيانات والتسلسلات الهرمية في جميع أنحاء علوم الحاسوب.
History
أنتجت دراسة كيرشوف للشبكات الكهربائية في القرن التاسع عشر نظرية مصفوفة الشجرة، بينما أصبح عد كايلي للأشجار الموسومة عام 1889 أحد أشهر الصيغ في نظرية الرسم البياني التعدادية.
Key figures
- Arthur Cayley
- Gustav Kirchhoff
- Heinz Prufer
Related topics
Seminal works
- diestel2017
- stanley2011
Frequently asked questions
- لماذا تحتوي الشجرة على n رأسًا على n-1 حافة بالضبط؟
- الشجرة متصلة، مما يفرض وجود n-1 حافة على الأقل، ولا دورية، مما يمنع وجود المزيد؛ يحدد الشرطان معًا عدد الحواف عند n-1 بالضبط.
- ما هو استخدام الشجرة الشاملة؟
- توفر الشجرة الشاملة مجموعة دنيا من الاتصالات التي تحافظ على اتصال الشبكة، وهو الأساس للبث الفعال وتصميم الشبكات الأقل تكلفة.