شجرة فائقة (نظرية البيان)
المحتويات

تعريفًا بالموضوع، في الرياضيات، يُسمى البيان فائق شجرة فائقة إذا أمكن إيجاد رسم بياني مضيف تمثل شجرة . بمعنى آخر، هو شجرة فائقة إذا كان هناك شجرة T بحيث كل hyperedge من H هو مجموعة من رؤوس الشجرة الفرعية المتصلة T. يطلق على الأشجار الفائقة كذلك مسمى رسوم فائقيه شجريه( arboreal hypergraphs \tree hypergraphs). وتعرض الأقسام التالية جوانب أخرى من الموضوع.
ومن جهة أخرى، كل شجرة هي كذلك شجرة فائقة ويكن كذلك استخدامها كرسم بياني مضيف، وكل ضلع في T يشكل شجرة فرعية من هذا الرسم البياني المضيف. لذلك، يمكن اعتبار الشجرة الفائقة في الرسوم الفائقة كتعميم لمفهوم شجرة في الرسم البياني . هذا التعريف للبيان فائق يشمل الرسوم الفائقة المتصلة بدون دورات بيرغ ( Berge-acyclic)، والتي تم استخدامها كذلك كتعميم (ربما مختلف) للأشجار للرسومات الفائقية.
الخصائص
وفي هذا السياق، كل شجرة فائقة لها خاصية Helly (2-Helly property ) والتي تنص على أنه إذا كانت S مجموعة جزئية من الأضلاع الفائقة بحيث أن كل تقاطع أي ضلعين فائقيين فيها هي مجموعة غير خالية فإن المجموعة فإن S نفسها بها تقاطع غير خالي (يوجد رأس ينتمي إلى كل ضلع فائقي في S ).
وفي السياق ذاته، نقول أن البيان فائق هو شجرة فائقة إذا وفقط إذا كان لديه خاصية Helly والرسم البياني الخطي هو رسم بياني وتري .
علاوةً على ذلك، من خلال نتائج Duchet و Flament و Slater يمكن تعريف أي شجرة فائقة بشكل مكافئ بأحد الخصائص التالية:
ومن ناحية أخرى، يكون البيان فائق شجرة فائقة إذا وفقط إذا كانت البيان فائق المزدوج له لايحتوي على دورة ألفا ( alpha-acyclic) تبعا لتعريف الباحث Fagin.
وفي هذا الصدد، البيان فائق يكون شجرة فائقة إذا وفقط إذا كان لها البيان فائق المزدوج له هو متواز (conformal ) و الرسم البياني بقسمين للبيان فائق المزدود هو وتري (chordal) .
في هذا الإطار، من الممكن التعرف على البيان فائق (كمزدوج لرسم فائقي بدون دورة ألفا ) في زمن خطي . مسألة الغطاء الدقيق (وهي العثور على مجموعة من الأضلاع الفائقة غير المتقاطعة التي تغطي جميع الرؤوس) قابلة للحل في وقت متعدد الحدود للأشجار الفائقة لكنها تظل مسألة كثيرة حدود غير قطعية كاملة للرسومات الفائقة بدون دورة ألفا.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟