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