شجرة زائدية (نظرية الرسومات)

في الرياضيات، يُسمى الرسم الزائدي  شجرة زائدية (hypertree ) إذا أمكن إيجاد رسم بياني مضيف  تمثل شجرة . بمعنى آخر، هو شجرة زائدية إذا كان هناك شجرة T بحيث كل hyperedge من H هو مجموعة من رؤوس الشجرة الفرعية المتصلة T.  يطلق على الأشجار الزائدية أيضًا مسمى رسوم زائديه شجريه( arboreal hypergraphs  \tree hypergraphs).

كل شجرة  هي أيضا شجرة زائدية ويكن أيضا استخدامها كرسم بياني مضيف، وكل ضلع في T يشكل شجرة فرعية من هذا الرسم البياني المضيف. لذلك، يمكن اعتبار الشجرة الزائدية في الرسوم الزائدية كتعميم لمفهوم شجرة في الرسم البياني . هذا التعريف للرسم الزائدي يشمل الرسوم الزائدية المتصلة بدون دورات بيرغ ( Berge-acyclic)، والتي تم استخدامها أيضًا كتعميم (ربما مختلف) للأشجار للرسومات الزائدية.

الخصائص 
كل شجرة زائدية لها خاصية Helly (2-Helly property ) والتي تنص على أنه إذا كانت S مجموعة جزئية من الأضلاع الزائدية بحيث أن كل تقاطع أي ضلعين زائديين فيها هي مجموعة غير خالية فإن المجموعة فإن S نفسها بها تقاطع غير خالي (يوجد رأس ينتمي إلى كل ضلع زائدي في S ).

من خلال نتائج Duchet و Flament و Slater  يمكن تعريف أي شجرة زائدية بشكل مكافئ بأحد الخصائص التالية:

 نقول أن الرسم الزائدي  هو شجرة زائدية إذا وفقط إذا كان لديه خاصية Helly والرسم البياني الخطي هو رسم بياني وتري .
 الرسم الزائدي  يكون شجرة زائدية إذا وفقط إذا كان لها الرسم الزائدي المزدوج له هو متواز (conformal ) و الرسم البياني بقسمين للرسم الزائدي المزدود  هو وتري (chordal) .
 يكون الرسم الزائدي شجرة زائدية إذا وفقط إذا كانت الرسم الزائدي المزدوج له لايحتوي على دورة ألفا ( alpha-acyclic) تبعا لتعريف الباحث Fagin.

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

انظر أيضا 

 رسم بياني وتري مزدوج وهو رسم بياني الذي به أكبر عصبة به يمثل شجرة زائدية.

ملاحظات

المراجع 

 
 .
 .
 .
 .
 .
 .
 .
 .

أشجار (نظرية المخططات)
نظرية المخططات