عرض مصدر شجرة فائقة (نظرية البيان)

{{يتيمة|تاريخ=أغسطس 2019}}

[[ملف:Hypertree.svg|تصغير|شجرة فائقة برؤوس زرقاء و أضلاع فائقة ملونه بالأصفر) وشجرة المضيف (أحمر)]]
في الرياضيات، يُسمى [[بيان فائق|البيان فائق]] <math>H</math> '''شجرة فائقة ''' {{إنج|hypertree}} إذا أمكن إيجاد رسم بياني مضيف ''<math> T</math>'' تمثل [[شجرة (نظرية المخططات)|شجرة]] . بمعنى آخر، <math>H</math>هو شجرة فائقة إذا كان هناك شجرة ''T'' بحيث كل hyperedge من ''H'' هو مجموعة من رؤوس الشجرة الفرعية المتصلة ''T.'' <ref>{{Harvard citation text|Brandstädt|Dragan|Chepoi|Voloshin|1998}}</ref> يطلق على الأشجار الفائقة أيضًا مسمى رسوم '''فائقيه شجريه( arboreal hypergraphs''' <ref name="مولد تلقائيا2">{{Harvard citation text|Berge|1989}}</ref> \'''tree hypergraphs'''<ref>{{Harvard citation text|McKee|McMorris|1999}}</ref>).

كل [[شجرة (نظرية المخططات)|شجرة]] <math>T</math> هي أيضا شجرة فائقة ويكن أيضا استخدامها كرسم بياني مضيف، وكل ضلع في ''T'' يشكل [[شجرة (بنية بيانات)|شجرة فرعية]] من هذا الرسم البياني المضيف. لذلك، يمكن اعتبار الشجرة الفائقة في الرسوم الفائقة كتعميم لمفهوم شجرة في الرسم البياني .<ref name="مولد تلقائيا1">{{Harvard citation text|Berge|1989}}; {{Harvard citation text|Voloshin|2002}}</ref> هذا التعريف للبيان فائق يشمل الرسوم الفائقة المتصلة بدون دورات بيرغ ( Berge-acyclic)، والتي تم استخدامها أيضًا كتعميم (ربما مختلف) للأشجار للرسومات الفائقية.

== الخصائص ==
كل شجرة فائقة لها [[:en:Helly family|خاصية Helly]] (2-Helly property ) والتي تنص على أنه إذا كانت ''S'' مجموعة جزئية من الأضلاع الفائقة بحيث أن كل تقاطع أي ضلعين فائقيين فيها هي مجموعة غير خالية فإن المجموعة فإن ''S'' نفسها بها تقاطع غير خالي (يوجد رأس ينتمي إلى كل ضلع فائقي في ''S'' ).<ref name="مولد تلقائيا1" />

من خلال نتائج Duchet و Flament و Slater <ref>See, e.g., {{Harvard citation text|Brandstädt|Le|Spinrad|1999}}; {{Harvard citation text|McKee|McMorris|1999}}</ref> يمكن تعريف أي شجرة فائقة بشكل مكافئ بأحد الخصائص التالية:

* نقول أن البيان فائق <math>H</math> هو شجرة فائقة إذا وفقط إذا كان لديه [[:en:Helly family|خاصية Helly]] والرسم البياني الخطي هو [[:en:Chordal graph|رسم بياني وتري]] .
* البيان فائق <math>H</math> يكون شجرة فائقة إذا وفقط إذا كان لها [[رسم فائقي|البيان فائق المزدوج]] له <math>H^*</math>هو متواز ([[:en:Conformal hypergraph|conformal]] ) و الرسم البياني بقسمين ''للبيان فائق المزدود'' <math>H^*</math> هو [[:en:Chordal graph|وتري]] (chordal) .<ref name="مولد تلقائيا2" />
* يكون البيان فائق شجرة فائقة إذا وفقط إذا كانت [[رسم فائقي|البيان فائق المزدوج]] له لايحتوي على دورة ألفا ( [[:en:Alpha-acyclic|alpha-acyclic]]) تبعا لتعريف الباحث Fagin.<ref>{{Harvard citation text|Fagin|1983}}</ref>

من الممكن التعرف على البيان فائق (كمزدوج لرسم فائقي بدون دورة ألفا ) في زمن [[تعقيد الوقت|خطي]] . {{Sfnp|Tarjan|Yannakakis|1984}} مسألة [[:en:Exact cover|الغطاء الدقيق]] (وهي العثور على مجموعة من الأضلاع الفائقة غير المتقاطعة التي تغطي جميع الرؤوس) قابلة للحل في وقت متعدد الحدود للأشجار الفائقة لكنها تظل [[مسألة كثيرة حدود غير قطعية كاملة]] للرسومات الفائقة بدون دورة ألفا.<ref>{{Harvard citation text|Brandstädt|Leitert|Rautenbach|2012}}</ref>

== انظر أيضا ==

* [[:en:Dually chordal graph|رسم بياني وتري مزدوج]] وهو رسم بياني الذي به أكبر عصبة به يمثل شجرة فائقية.

== ملاحظات ==

{{مراجع}}
{{شريط بوابات|رياضيات|علم الحاسوب}}

[[تصنيف:أشجار (نظرية البيان)]]